QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#342791 | #2557. Lag | bachbeo2007 | WA | 3ms | 36672kb | C++23 | 7.1kb | 2024-03-01 16:54:16 | 2024-03-01 16:54:16 |
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 getnew(int l,int r,int id,int val){
lazy[id]+=val;
tree[id]+=(r-l+1)*val;
}
void pushdown(int l,int r,int id){
if(!lazy[id]) return;
int mid=(l+r)>>1;
getnew(l,r,id<<1,lazy[id]);
getnew(mid+1,r,id<<1|1,lazy[id]);
lazy[id]=0;
}
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){
getnew(l,r,id,val);
return;
}
pushdown(l,r,id);
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];
pushdown(l,r,id);
int mid=(l+r)>>1;
if(p<=mid) return query(l,mid,id<<1,p);
else return tree[id<<1]+query(mid+1,r,id<<1|1,p);
}
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<=2*Max;i++) f0.bit[i]=f1.bit[i]=f2.bit[i]=0;
for(int i=0;i<=Max;i++) pos[i].clear();
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(y1==y2) q1.push_back({y1,x1,y2,x2,val});
else if(x1==x2) q0.push_back({x1,y1,x2,y2,val});
else if(x1-y1==x2-y2) q2.push_back({x1,y1,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();
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 3ms
memory: 36672kb
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 3 1
result:
wrong answer 2nd words differ - expected: '2', found: '3'