Submission #862988

#TimeUsernameProblemLanguageResultExecution timeMemory
862988HuyQuang_re_ZeroPairs (IOI07_pairs)C++14
37 / 100
1878 ms275864 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define ll long long #define db long double #define N 1005 #define II pair <ll,ll> #define III pair <ll,II> #define IV pair <vector <int>,vector <int> > #define fst first #define snd second #define BIT(x,i) ((x>>i)&1) #define pi acos(-1) #define to_radian(x) (x*pi/180.0) #define to_degree(x) (x*180.0/pi) #define rand(l,r) (l+rng()%(r-l+1)) using namespace std; using namespace __gnu_pbds; struct _1D_Problem { ll n,d,x[100005],i,j,res,m; void Work() { cin>>n>>d>>m; for(i=1;i<=n;i++) cin>>x[i]; sort(x+1,x+n+1); j=1; for(i=1;i<=n;i++) { while(x[i]-x[j]>d) j++; res+=i-j; } cout<<res; } } Line; struct _2D_Problem { typedef tree <II,null_type,less <II>,rb_tree_tag,tree_order_statistics_node_update> ordered_set; struct Fenwick_Tree { ordered_set bit[75005]; map <int,int> cnt; void update(int i,int k) { II x={ k,++cnt[k] }; while(i<=75000) bit[i].insert(x),i+=(i & -i); } int get(int i,int k) { int res=0; while(i>=1) res+=bit[i].size()-bit[i].order_of_key({ k,0 }),i-=(i & -i); return res; } } SUM,SUB; II a[N]; ll n,d,m,i,res; void Work() { cin>>n>>d>>m; for(i=1;i<=n;i++) cin>>a[i].fst>>a[i].snd; sort(a+1,a+n+1); ll res=0; for(i=1;i<=n;i++) { res+=SUM.get(a[i].snd,a[i].fst+a[i].snd-d); res+=SUB.get(m,a[i].fst-a[i].snd-d)-SUB.get(a[i].snd,a[i].fst-a[i].snd-d); SUM.update(a[i].snd,a[i].fst+a[i].snd); SUB.update(a[i].snd,a[i].fst-a[i].snd); } cout<<res; } } Grid; struct _3D_Problem { struct pt { int x,y,z; } a[100005]; ll res,c[76][76][76]; int f[76][76][76][2*75+1],x,y,z,z1,z2,i,n,m,d,step,sum; void Work() { cin>>n>>d>>m; for(i=1;i<=n;i++) cin>>a[i].x>>a[i].y>>a[i].z; for(step=1;step<=4;step++) { memset(f,0,sizeof(d)); memset(c,0,sizeof(c)); for(i=1;i<=n;i++) { f[a[i].z][a[i].x][a[i].y][a[i].x+a[i].y]++; c[a[i].x][a[i].y][a[i].z]++; } for(z=1;z<=m;z++) for(x=1;x<=m;x++) for(y=1;y<=m;y++) for(sum=2*m;sum>=1;sum--) { f[z][x][y][sum]+=f[z][x-1][y][sum]; f[z][x][y][sum]+=f[z][x][y-1][sum]; f[z][x][y][sum]+=f[z][x][y][sum+1]; f[z][x][y][sum]-=f[z][x-1][y-1][sum]; f[z][x][y][sum]-=f[z][x][y-1][sum+1]; f[z][x][y][sum]-=f[z][x-1][y][sum+1]; f[z][x][y][sum]+=f[z][x-1][y-1][sum+1]; // if(f[z][x][y][sum]>0) // cout<<z<<" "<<x<<" "<<y<<" "<<sum<<'\n'; } for(z1=1;z1<=m;z1++) for(z2=1;z2<=z1;z2++) for(x=1;x<=m;x++) for(y=1;y<=m;y++) { if(z1!=z2 || step<=2) res+=c[x][y][z1]*f[z2][x-1][y][max(1,x+y+z1-z2-d)]; // if(step==2 && z1==10 && x==20 && y==11) cerr<<c[x][y][z1]<<'\n'; // cerr<<f[z2][x-1][y][max(1,x+y+z1-z2-d)]<<'\n'; } for(i=1;i<=n;i++) swap(a[i].x,a[i].y),a[i].y=m-a[i].y+1; } for(z1=1;z1<=m;z1++) { for(x=1;x<=m;x++) for(y=1;y<=m;y++) { for(z2=max(1,z1-d);z2<z1;z2++) res+=c[x][y][z1]*c[x][y][z2]; res+=c[x][y][z1]*(c[x][y][z1]-1)/2; } } cout<<res<<'\n'; } } Cube; int main() { // freopen("pairs.inp","r",stdin); //freopen("pairs.out","w",stdout); ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int type; cin>>type; if(type==1) Line.Work(); if(type==2) Grid.Work(); if(type==3) Cube.Work(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...