Submission #891195

#TimeUsernameProblemLanguageResultExecution timeMemory
891195Faisal_SaqibPairs (IOI07_pairs)C++17
92 / 100
1726 ms524288 KiB
#pragma optimze("Ofast") #include <iostream> #include <vector> #include <algorithm> #include <bitset> using namespace std; // #define endl '\n' const int N=76; int pre[N][N][N]; // bool have1[N]; bitset<100> have1; int have3[N][N][N]; int main() { ios::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL); int b,m; cin>>b; if(b==1) { int n,d; cin>>n>>d>>m; vector<int> a; for(int i=0;i<n;i++) { int x; cin>>x; a.push_back(x); } long long cnt=0; sort(begin(a),end(a)); int i=0; for(int j=0;j<n;j++) { while(i<n and a[i]<(a[j]-d)) { i++; } cnt+=(j-i); } cout<<cnt<<'\n'; } else if(b==2) { // exit(-1); int n,d; cin>>n>>d>>m; vector<pair<int,int>> a; vector<vector<int>> pre1; vector<int> ap; // for(int i=0;i<=m;i++) // ap.push_back(0); for(int j=0;j<=m;j++) pre1.push_back(ap); for(int i=0;i<n;i++) { int x,y; cin>>x>>y; a.push_back({x,y}); while(pre1[x].size()<=m) { pre1[x].push_back(0); } while(y<=m) { pre1[x][y]++; y++; } } long long cnt=0; for(int i=0;i<n;i++) { int x=a[i].first; int y=a[i].second; for(int dx=0;dx<=d and dx<=(m-1);dx++) { int dy=d-dx; if((x+dx)<=m and pre1[x+dx].size()>0) { cnt+=(pre1[(x+dx)][min(m,y+dy)]-pre1[x+dx][max(0,y-dy-1)])-(dx==0); } if((x-dx)>0 and dx!=0 and pre1[x-dx].size()>0) { cnt+=(pre1[(x-dx)][min(m,y+dy)]-pre1[x-dx][max(0,y-dy-1)]); } } // cout<<"For "<<i<<' '<<cnt<<endl; } cout<<cnt/2<<'\n'; } else { int n,d; cin>>n>>d>>m; vector<pair<int,pair<int,int>>> a; for(int i=0;i<n;i++) { int x,y,z; cin>>x>>y>>z; a.push_back({x,{y,z}}); have1[x]=1; have3[x][y][z]++; while(z<=m) { pre[x][y][z]++; z++; } } long long cnt=0; d=min(d,(m-1)*b); sort(begin(a),end(a)); a.resize(unique(begin(a),end(a))-begin(a)); for(int i=0;i<a.size();i++) { int x=a[i].first,y=a[i].second.first,z=a[i].second.second; int p=0; for(int dx=0;dx<=(d) and dx<=(m-1);dx++) { if((x+dx>m or !have1[x+dx]) and ((x-dx)<=0 or !have1[x-dx])) continue; for(int dy=0;dy<=(m-1) and dy<=d and (dy+dx)<=d and (dy+dx)<=(2*(m-1));dy++) { int dz=d-(dy+dx); if((x+dx)<=m) { if((y+dy)<=m) { p+=(pre[x+dx][y+dy][min(m,z+dz)]-pre[x+dx][y+dy][max(0,z-dz-1)])-((dx==0) and (dy==0)); } if((y-dy)>0 and (dy!=0)) { p+=(pre[x+dx][y-dy][min(m,z+dz)]-pre[x+dx][y-dy][max(0,z-dz-1)])-((dx==0) and (dy==0)); } } if((x-dx)>0 and (dx!=0)) { if((y+dy)<=m) { p+=(pre[x-dx][y+dy][min(m,z+dz)]-pre[x-dx][y+dy][max(0,z-dz-1)])-((dx==0) and (dy==0)); } if((y-dy)>0 and (dy!=0)) { p+=(pre[x-dx][y-dy][min(m,z+dz)]-pre[x-dx][y-dy][max(0,z-dz-1)])-((dx==0) and (dy==0)); } } } } cnt+=p*have3[x][y][z]; } cout<<cnt/2<<'\n'; } return 0; }

Compilation message (stderr)

pairs.cpp:1: warning: ignoring '#pragma optimze ' [-Wunknown-pragmas]
    1 | #pragma optimze("Ofast")
      | 
pairs.cpp: In function 'int main()':
pairs.cpp:61:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   61 |    while(pre1[x].size()<=m)
      |          ~~~~~~~~~~~~~~^~~
pairs.cpp:114:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |   for(int i=0;i<a.size();i++)
      |               ~^~~~~~~~~
#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...