QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#342732 | #2557. Lag | bachbeo2007 | WA | 4ms | 25960kb | C++23 | 6.7kb | 2024-03-01 15:50:57 | 2024-03-01 15:50:57 |
Judging History
answer
// Judges with GCC >= 12 only needs Ofast
// #pragma GCC optimize("O3,no-stack-protector,fast-math,unroll-loops,tree-vectorize")
// MLE optimization
// #pragma GCC optimize("conserve-stack")
// Old judges
// #pragma GCC target("sse4.2,popcnt,lzcnt,abm,mmx,fma,bmi,bmi2")
// New judges. Test with assert(__builtin_cpu_supports("avx2"));
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")
// Atcoder
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma")
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
- insert(x),erase(x)
- find_by_order(k): return iterator to the k-th smallest element
- order_of_key(x): the number of elements that are strictly smaller
*/
#include<bits/stdc++.h>
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
uniform_real_distribution<> pp(0.0,1.0);
#define int long long
#define ld long double
#define pii pair<int,int>
#define piii pair<int,pii>
#define mpp make_pair
#define fi first
#define se second
const int inf=1e18;
const int mod=998244353;
const int maxn=250005;
const int bl=650;
const int maxs=655;
const int maxm=200005;
const int maxq=1000005;
const int maxl=20;
const int Max=250001;
const int root=3;
int power(int a,int n){
int res=1;
while(n){
if(n&1) res=res*a%mod;
a=a*a%mod;n>>=1;
}
return res;
}
const int iroot=power(3,mod-2);
const int base=101;
int dx[]={1,1,0,-1,-1,-1,0,1},
dy[]={0,1,1,1,0,-1,-1,-1};
int n,m,q;
int res[maxn];
int X[maxn],Y[maxn];
bool mv[maxn];
struct Rec{
int x1,y1,x2,y2;
Rec(){}
}rec[maxn];
struct Query{
int x1,y1,x2,y2,val;
};
namespace Left_to_Right{
int tree[4*maxn],lazy[4*maxn];
void update(int l,int r,int id,int tl,int tr,int val){
if(tr<l || r<tl) return;
if(tl<=l && r<=tr){
lazy[id]+=val;
tree[id]+=(r-l+1)*val;
return;
}
int mid=(l+r)>>1;
update(l,mid,id<<1,tl,tr,val);update(mid+1,r,id<<1|1,tl,tr,val);
tree[id]=tree[id<<1]+tree[id<<1|1];
}
int query(int l,int r,int id,int p){
if(l==r) return tree[id];
int mid=(l+r)>>1;
if(p<=mid) return query(l,mid,id<<1,p)+(p-l+1)*lazy[id];
else return tree[id<<1]+query(mid+1,r,id<<1|1,p)+(p-l+1)*lazy[id];
}
vector<piii> pos[maxn];
void solve(vector<Query> Q,vector<piii> qq){
for(int i=0;i<=Max;i++) pos[i].clear();
for(int i=0;i<=4*Max;i++) tree[i]=lazy[i]=0;
for(auto c:Q) pos[c.x1].push_back({c.val,{c.y1,c.y2}});
for(auto p:qq) pos[p.se.fi].push_back({0,{p.fi,p.se.se}});
for(int i=0;i<=Max;i++){
for(auto p:pos[i]){
if(p.fi) update(0,Max,1,p.se.fi,p.se.se,p.fi);
else res[p.se.fi]+=query(0,Max,1,p.se.se);
}
}
}
}
namespace Down_to_Up{
vector<pii> pos[maxn];
struct bit{
int bit[2*maxn];
void update(int x,int val){
assert(x>0);
for(int i=x;i<=2*Max;i+=(i&(-i))) bit[i]+=val;
}
int query(int x){
assert(x>=0);
int total=0;
for(int i=x;i>=1;i-=(i&(-i))) total+=bit[i];
return total;
}
}f0,f1,f2;
void cal(vector<Query> Q,vector<piii> qq){
for(int i=0;i<(int)Q.size();i++){
auto c=Q[i];
pos[c.x1].emplace_back(inf,i);
pos[c.x2+1].emplace_back(-inf,i);
}
for(auto p:qq) if(p.se.fi>=0) pos[p.se.fi].emplace_back(p.fi,p.se.se);
for(int i=0;i<=Max;i++){
for(auto p:pos[i]){
if(p.fi==-inf){
int d=Q[p.se].x1-Q[p.se].y1,val=Q[p.se].val;
f0.update(Max-d,-val);
f1.update(Max-d,val*(Q[p.se].x1-1));
f2.update(Max-d,val*(Q[p.se].x2-Q[p.se].x1+1));
}
else if(p.fi==inf){
int d=Q[p.se].x1-Q[p.se].y1,val=Q[p.se].val;
f0.update(Max-d,val);
f1.update(Max-d,-val*(i-1));
}
else{
res[p.fi]+=f0.query(Max-(i-p.se))*i+f1.query(Max-(i-p.se))+f2.query(Max-(i-p.se));
}
}
}
}
void solve(vector<Query> Q,vector<piii> qq){
cal(Q,qq);
for(auto &c:Q){
swap(c.x1,c.y1);
swap(c.x2,c.y2);
}
for(auto &p:qq){
p.se.fi--;
swap(p.se.fi,p.se.se);
}
cal(Q,qq);
}
}
void solve(){
cin >> n >> m >> q;
for(int i=1;i<=n;i++) cin >> rec[i].x1 >> rec[i].y1 >> rec[i].x2 >> rec[i].y2;
vector<Query> q0,q1,q2,q3;
auto add = [&](int x1,int y1,int x2,int y2,int val){
if(x1>x2 || (x1==x2 && y1>y2)){
swap(x1,x2);
swap(y1,y2);
}
if(x1==x2) q0.push_back({x1,y1,x2,y2,val});
else if(y1==y2) q1.push_back({y1,x1,y2,x2,val});
else if(x1-y1==x2-y2) q2.push_back({x1,y2,x2,y2,val});
else q3.push_back({Max-x2+1,y2,Max-x1+1,y1,-val});
};
for(int i=1;i<=m;i++){
int id,p,d;cin >> id >> p >> d;
Rec S=rec[p];
S.x1+=dx[id]*mv[p];
S.y1+=dy[id]*mv[p];
S.x2+=dx[id]*mv[p];
S.y2+=dy[id]*mv[p];
mv[p]=true;
rec[p].x1+=dx[id]*d;
rec[p].y1+=dy[id]*d;
rec[p].x2+=dx[id]*d;
rec[p].y2+=dy[id]*d;
Rec T=rec[p];
add(S.x1,S.y1,T.x1,T.y1,1);
add(S.x2+1,S.y1,T.x2+1,T.y1,-1);
add(S.x1,S.y2+1,T.x1,T.y2+1,-1);
add(S.x2+1,S.y2+1,T.x2+1,T.y2+1,1);
}
for(int i=1;i<=n;i++){
if(mv[i]) continue;
Rec S=rec[i],T=S;
add(S.x1,S.y1,T.x1,T.y1,1);
add(S.x2+1,S.y1,T.x2+1,T.y1,-1);
add(S.x1,S.y2+1,T.x1,T.y2+1,-1);
add(S.x2+1,S.y2+1,T.x2+1,T.y2+1,1);
}
vector<piii> qq;
for(int i=0;i<q;i++){
cin >> X[i] >> Y[i];
qq.push_back({i,{X[i],Y[i]}});
}
Left_to_Right::solve(q0,qq);
Down_to_Up::solve(q2,qq);
for(int i=0;i<q;i++){
qq[i].se.fi=Y[i];
qq[i].se.se=X[i];
}
Left_to_Right::solve(q1,qq);
for(int i=0;i<q;i++){
qq[i].se.fi=Max-1-X[i];
qq[i].se.se=Y[i];
}
Down_to_Up::solve(q3,qq);
for(int i=0;i<q;i++) cout << res[i] << '\n';
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);
int test=1;//cin >> test;
while(test--) solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 4ms
memory: 25372kb
input:
1 8 3 2 1 2 1 0 1 1 1 1 1 2 1 1 3 1 1 4 1 1 5 1 1 6 1 1 7 1 1 1 1 2 1 4 2
output:
0 2 1
result:
ok 3 tokens
Test #2:
score: 0
Accepted
time: 0ms
memory: 25268kb
input:
2 0 3 3 3 7 7 4 4 6 6 5 5 3 7 8 8
output:
2 1 0
result:
ok 3 tokens
Test #3:
score: -100
Wrong Answer
time: 0ms
memory: 25960kb
input:
10 10 10 45066 44774 106240 221436 22774 27403 164972 196292 35788 27798 154149 71660 8624 14258 47662 205040 9479 49585 89304 70902 24893 32999 218506 41529 27023 49837 175362 52663 21858 40287 135949 41957 12106 48095 80386 230759 41236 37600 169685 129218 7 6 5009 4 5 2577 0 5 37640 3 10 34168 1 ...
output:
-2431023 -3205413 -1891710 -2107589 -2405717 -3259521 -2895810 -3556655 -3291588 -2665933
result:
wrong answer 1st words differ - expected: '0', found: '-2431023'