제출 #355633

#제출 시각아이디문제언어결과실행 시간메모리
355633ogibogi2004Pairs (IOI07_pairs)C++14
100 / 100
503 ms88300 KiB
#include<bits/stdc++.h> using namespace std; #define ll long long ll b,n,d,m; void solve1() { vector<ll>v; for(ll i=1;i<=n;i++) { ll x; cin>>x; v.push_back(x); } sort(v.begin(),v.end()); queue<ll>q; long long ans=0; for(ll i=0;i<v.size();i++) { q.push(v[i]); while(v[i]-q.front()>d) { q.pop(); } ans+=q.size()-1; } cout<<ans<<endl; } vector<ll>animals[500000]; ll bit[500000]; void update(ll idx,ll val) { idx++; for(;idx<500000;idx+=idx&(-idx)) { bit[idx]+=val; } } ll query(ll idx) { //cout<<idx<<endl; idx++; ll ret=0; for(;idx>0;idx-=idx&(-idx)) { ret+=bit[idx]; } return ret; } ll query(ll l,ll r) { return query(r)-query(l-1); } void solve2() { vector<pair<ll,ll> >v; ll min1=(ll)1e9,min2=(ll)1e9; for(ll i=1;i<=n;i++) { ll x,y; cin>>x>>y; v.push_back({x-y,x+y}); min1=min(min1,v.back().first); min2=min(min2,v.back().second); } for(ll i=0;i<v.size();i++) { v[i].first-=min1; v[i].second-=min2; } for(auto xd:v) { animals[xd.first].push_back(xd.second); } ll ans=0; for(ll i=0;i<500000;i++) { //cout<<i<<endl; sort(animals[i].begin(),animals[i].end()); if(i-d-1>=0) { for(auto a:animals[i-d-1]) { update(a,-1); } } for(auto a:animals[i]) { ans+=query(a-d,a+d); update(a,+1); } } cout<<ans<<endl; } ll bit3[400][400][400]; void update3(ll idx1,ll idx2,ll idx3,ll val) { idx1++; idx2++; idx3++; for(ll i1=idx1;i1<400;i1+=i1&(-i1)) for(ll i2=idx2;i2<400;i2+=i2&(-i2)) for(ll i3=idx3;i3<400;i3+=i3&(-i3)) { bit3[i1][i2][i3]+=val; } } ll query3(ll idx1,ll idx2,ll idx3) { idx1++; idx2++; idx3++; if(idx1>=400)idx1=399; if(idx2>=400)idx2=399; if(idx3>=400)idx3=399; ll ans=0; for(ll i1=idx1;i1>0;i1-=i1&(-i1)) for(ll i2=idx2;i2>0;i2-=i2&(-i2)) for(ll i3=idx3;i3>0;i3-=i3&(-i3)) { ans+=bit3[i1][i2][i3]; } return ans; } ll query3(ll x1,ll y1,ll z1,ll x2,ll y2,ll z2) { return query3(x2,y2,z2)-query3(x1-1,y2,z2)-query3(x2,y1-1,z2)-query3(x2,y2,z1-1)+query3(x2,y1-1,z1-1)+query3(x1-1,y2,z1-1)+query3(x1-1,y1-1,z2)-query3(x1-1,y1-1,z1-1); } struct point { ll x,y,z; bool operator<(point const& other)const { return make_pair(x,make_pair(y,z))<make_pair(other.x,make_pair(other.y,other.z)); } }; vector<point>ivan[400]; void solve3() { ll min1,min2,min3=(ll)1e9; min1=min3;min2=min3; for(ll i=1;i<=n;i++) { ll a,b,c; cin>>a>>b>>c; ivan[a+b+c].push_back({a+b-c,a-b+c,a-b-c}); min1=min(min1,ivan[a+b+c].back().x); min2=min(min2,ivan[a+b+c].back().y); min3=min(min3,ivan[a+b+c].back().z); } for(ll i=0;i<400;i++) { for(ll j=0;j<ivan[i].size();j++) { ivan[i][j].x-=min1; ivan[i][j].y-=min2; ivan[i][j].z-=min3; } } ll ans=0; for(ll i=0;i<400;i++) { sort(ivan[i].begin(),ivan[i].end()); if(i-d-1>=0) { for(auto a:ivan[i-d-1]) { update3(a.x,a.y,a.z,-1); } } for(auto a:ivan[i]) { //cout<<i<<" "<<a.x<<" "<<a.z<<" "<<a.y<<endl; ans+=query3(a.x-d,a.y-d,a.z-d,a.x+d,a.y+d,a.z+d); update3(a.x,a.y,a.z,+1); } } cout<<ans<<endl; } int main() { cin>>b>>n>>d>>m; if(b==1)solve1(); if(b==2)solve2(); if(b==3)solve3(); return 0; }

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

pairs.cpp: In function 'void solve1()':
pairs.cpp:17:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |  for(ll i=0;i<v.size();i++)
      |             ~^~~~~~~~~
pairs.cpp: In function 'void solve2()':
pairs.cpp:65:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |  for(ll i=0;i<v.size();i++)
      |             ~^~~~~~~~~
pairs.cpp: In function 'void solve3()':
pairs.cpp:152:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  152 |   for(ll j=0;j<ivan[i].size();j++)
      |              ~^~~~~~~~~~~~~~~
#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...