QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#342725 | #2557. Lag | bachbeo2007 | RE | 9ms | 24936kb | C++23 | 6.6kb | 2024-03-01 15:39:24 | 2024-03-01 15:39:24 |
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){
for(int i=x;i<=2*Max;i+=(i&(-i))) bit[i]+=val;
}
int query(int x){
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[i].x1-Q[i].y1,val=Q[i].val;
f0.update(Max-d,-val);
f1.update(Max-d,val*(Q[i].x1-1));
f2.update(Max-d,val*(Q[i].x2-Q[i].x1+1));
}
else if(p.fi==inf){
int d=Q[i].x1-Q[i].y1,val=Q[i].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-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: 100
Accepted
time: 4ms
memory: 24596kb
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: 9ms
memory: 24936kb
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
Runtime Error
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 ...