Submission #113426

#TimeUsernameProblemLanguageResultExecution timeMemory
113426TadijaSebezPairs (IOI07_pairs)C++11
60 / 100
166 ms26036 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long void Solve1D() { int n,d,m,i; scanf("%i %i %i",&n,&d,&m); vector<int> x(n); for(int i=0;i<n;i++) scanf("%i",&x[i]); sort(x.begin(),x.end()); int j=0; ll ans=0; for(int i=0;i<n;i++) { while(x[i]-x[j]>d) j++; ans+=i-j; } printf("%lld\n",ans); } const int N=100050; const int lim=2*N; int x[N],y[N],sum[N],dif[N],id[N]; const int M=20*N; int ls[M],rs[M],tsz,root[N],cnt[M]; void Set(int p, int &c, int ss, int se, int qi, int f) { c=++tsz;ls[c]=ls[p];rs[c]=rs[p];cnt[c]=cnt[p]+f; if(ss==se) return; int mid=ss+se>>1; if(qi<=mid) Set(ls[p],ls[c],ss,mid,qi,f); else Set(rs[p],rs[c],mid+1,se,qi,f); } int Get(int p, int c, int ss, int se, int qs, int qe) { if(qs>qe || qs>se || ss>qe) return 0; if(qs<=ss && qe>=se) return cnt[c]-cnt[p]; int mid=ss+se>>1; return Get(ls[p],ls[c],ss,mid,qs,qe)+Get(rs[p],rs[c],mid+1,se,qs,qe); } void Solve2D() { int n,d,m,i; scanf("%i %i %i",&n,&d,&m); for(i=1;i<=n;i++) scanf("%i %i",&x[i],&y[i]),sum[i]=x[i]+y[i],dif[i]=x[i]-y[i],id[i]=i; sort(id+1,id+1+n,[&](int i, int j){ return sum[i]<sum[j];}); int l=1; ll ans=0; for(int j=1;j<=n;j++) { i=id[j]; Set(root[j-1],root[j],-lim,lim,dif[i],1); while(sum[i]-sum[id[l]]>d) l++; ans+=Get(root[l-1],root[j-1],-lim,lim,dif[i]-d,dif[i]+d); } printf("%lld\n",ans); } const int H=77*3; struct BIT3D { int sum[H][H][H]; BIT3D(){} void Add(int x, int y, int z, int f) { for(int i=x;i<H;i+=i&-i) for(int j=y;j<H;j+=j&-j) for(int k=z;k<H;k+=k&-k) sum[i][j][k]+=f; } int Get(int x, int y, int z) { int ans=0; for(int i=x;i;i-=i&-i) for(int j=y;j;j-=j&-j) for(int k=z;k;k-=k&-k) ans+=sum[i][j][k]; return ans; } int Get(int xl, int xr, int yl, int yr, int zl, int zr) { xl--;yl--;zl--; xl=max(0,xl); yl=max(0,yl); zl=max(0,zl); xr=min(xr,H-1); yr=min(yr,H-1); zr=min(zr,H-1); return Get(xr,yr,zr)-Get(xl,yr,zr)-Get(xr,yl,zr)-Get(xr,yr,zl)+Get(xl,yl,zr)+Get(xl,yr,zl)+Get(xr,yl,zl)-Get(xl,yl,zl); } } ST; int z[N]; void Solve3D() { int n,d,m,i; scanf("%i %i %i",&n,&d,&m); for(i=1;i<=n;i++) { scanf("%i %i %i",&x[i],&y[i],&z[i]); id[i]=i; } sort(id+1,id+1+n,[&](int i, int j){ return x[i]+y[i]+z[i]<x[j]+y[j]+z[j];}); int l=1; ll ans=0; for(int j=1;j<=n;j++) { int i=id[j]; while(x[i]+y[i]+z[i]-x[id[l]]-y[id[l]]-z[id[l]]>d) { int k=id[l]; ST.Add(n-x[k]+y[k]+z[k],n+x[k]-y[k]+z[k],n+x[k]+y[k]-z[k],-1); l++; } ans+=ST.Get(n-x[i]+y[i]+z[i]-d,n-x[i]+y[i]+z[i]+d,n+x[i]-y[i]+z[i]-d,n+x[i]-y[i]+z[i]+d,n+x[i]+y[i]-z[i]-d,n+x[i]+y[i]-z[i]+d); ST.Add(n-x[i]+y[i]+z[i],n+x[i]-y[i]+z[i],n+x[i]+y[i]-z[i],1); } printf("%lld\n",ans); } int main() { int B; scanf("%i",&B); if(B==1) Solve1D(); if(B==2) Solve2D(); if(B==3) Solve3D(); return 0; }

Compilation message (stderr)

pairs.cpp: In function 'void Solve1D()':
pairs.cpp:6:12: warning: unused variable 'i' [-Wunused-variable]
  int n,d,m,i;
            ^
pairs.cpp: In function 'void Set(int, int&, int, int, int, int)':
pairs.cpp:29:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=ss+se>>1;
             ~~^~~
pairs.cpp: In function 'int Get(int, int, int, int, int, int)':
pairs.cpp:37:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~
pairs.cpp: In function 'void Solve1D()':
pairs.cpp:7:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i %i",&n,&d,&m);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~
pairs.cpp:9:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=0;i<n;i++) scanf("%i",&x[i]);
                       ~~~~~^~~~~~~~~~~~
pairs.cpp: In function 'void Solve2D()':
pairs.cpp:43:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i %i",&n,&d,&m);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~
pairs.cpp:44:80: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(i=1;i<=n;i++) scanf("%i %i",&x[i],&y[i]),sum[i]=x[i]+y[i],dif[i]=x[i]-y[i],id[i]=i;
                    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~
pairs.cpp: In function 'void Solve3D()':
pairs.cpp:94:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i %i",&n,&d,&m);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~
pairs.cpp:97:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%i %i %i",&x[i],&y[i],&z[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
pairs.cpp: In function 'int main()':
pairs.cpp:120:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i",&B);
  ~~~~~^~~~~~~~~
#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...