제출 #1076734

#제출 시각아이디문제언어결과실행 시간메모리
1076734Faisal_SaqibPairs (IOI07_pairs)C++17
70 / 100
1759 ms6356 KiB
#pragma optimze("Ofast") #include <iostream> #include <vector> #include <algorithm> #include <bitset> using namespace std; // #define endl '\n' #define ll long long const int N=76; int pre[N][N][N]; #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; #define ordered_set tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> bitset<100> have1; int have3[N][N][N]; void solve_1d() { int n,d,m; 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'; } void solve_2d() { int n,d,m; cin>>n>>d>>m; vector<pair<int,int>> b; for(int i=0;i<n;i++) { int x,y; cin>>x>>y; b.push_back({x+y,x-y}); } ordered_set sp; ll cnt=0; sort(begin(b),end(b)); int j=0; for(int i=0;i<n;i++) { while(j<=i and (b[i].first-b[j].first)>d) { sp.erase(sp.upper_bound(b[j].second)); j++; } int l=b[j].second-d; int r=b[j].second+d; cnt+=sp.order_of_key(r+1); cnt-=sp.order_of_key(l); sp.insert(b[i].second); } cout<<cnt<<'\n'; } int main() { ios::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL); int b,m; cin>>b; if(b==1) { solve_1d(); } else if(b==2) { solve_2d(); } else { int n,d; cin>>n>>d>>m; long long ap1=n; ap1*=ap1; long long kp=(2e8); if(ap1<=kp) { vector<vector<int>> a; for(int i=0;i<n;i++) { int x,y,z; cin>>x>>y>>z; a.push_back({x,y,z}); } long long cnt=0; for(int i=0;i<n;i++) { for(int j=i+1;j<n;j++) { if((abs(a[i][0]-a[j][0])+abs(a[i][1]-a[j][1])+abs(a[i][2]-a[j][2]))<=d) { cnt++; } } } cout<<cnt<<'\n'; exit(0); } 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; }

컴파일 시 표준 에러 (stderr) 메시지

pairs.cpp:1: warning: ignoring '#pragma optimze ' [-Wunknown-pragmas]
    1 | #pragma optimze("Ofast")
      | 
pairs.cpp: In function 'int main()':
pairs.cpp:136:22: 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]
  136 |         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...