Submission #1078647

#TimeUsernameProblemLanguageResultExecution timeMemory
1078647doducanhExamination (JOI19_examination)C++14
0 / 100
1131 ms69188 KiB
///breaker #pragma GCC optimize("O3") #include<bits/stdc++.h> using namespace std; #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; #define ordered_set tree<pair<int,int>, null_type,less<pair<int,int> >, rb_tree_tag,tree_order_statistics_node_update> #define ll long long #define fi first #define se second #define ii pair<int,int> #define mp make_pair #define in(x) freopen(x,"r",stdin) #define out(x) freopen(x,"w",stdout) #define bit(x,i) ((x>>i)&1) #define lc (id<<1) #define rc ((id<<1)^1) const int maxn=1e5+7; const int sz=350; struct BIT { int t[maxn]; void add(int x,int val){for(;x;x-=(x&(-x)))t[x]+=val;} int get(int x){int res=0;for(;x<maxn;x+=(x&(-x)))res+=t[x];return res;} }t[(maxn)/sz+1]; struct Data { int x,y,z,id; }; int n,q; Data a[maxn]; Data qu[maxn]; int ans[maxn]; ordered_set s[maxn]; int pos(int x,vector<int>&v) { return lower_bound(v.begin(),v.end(),x)-v.begin()+1; } bool cmp(Data a,Data b) { return a.z>b.z; } void sol(void){ cin>>n>>q; vector<int>vx; vector<int>vy; for(int i=1;i<=n;i++){ cin>>a[i].x>>a[i].y; vx.push_back(a[i].x); vy.push_back(a[i].y); a[i].z=a[i].x+a[i].y; } for(int i=1;i<=q;i++){ cin>>qu[i].x>>qu[i].y>>qu[i].z; vx.push_back(a[i].x); vy.push_back(a[i].y); qu[i].id=i; } sort(vx.begin(),vx.end()); sort(vy.begin(),vy.end()); vx.erase(unique(vx.begin(),vx.end()),vx.end()); vy.erase(unique(vy.begin(),vy.end()),vy.end()); sort(a+1,a+n+1,cmp); sort(qu+1,qu+q+1,cmp); int l=1; for(int i=1;i<=n;i++){ int pos1=pos(a[i].x,vx); int pos2=pos(a[i].y,vy); t[(pos1-1)/sz].add(pos2,1); s[pos1].insert({pos2,i}); while(l<=q&&(i==n||qu[l].z>a[i+1].z)){ if(qu[l].z>a[i].z){ l++; continue; } pos1=pos(qu[l].x,vx); pos2=pos(qu[l].y,vy); int tmp=0; for(int i=(pos1-1)/sz+1; i<=(vx.size()-1)/sz; i++)tmp+=t[i].get(pos2); for(int i=pos1; i<((pos1-1)/sz+1)*sz; i++)tmp+=s[i].size()-s[i].order_of_key({pos2,0}); ans[qu[l].id]=tmp; l++; } } for(int i=1;i<=q;i++){ cout<<ans[i]<<"\n"; } } signed main(void) { // ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); int t=1; while(t--){ sol(); } // you should actually read the stuff at the bottom return 0; } /* stuff you should look for * int overflow, array bounds * special cases (n=1?) * do smth instead of nothing and stay organized * WRITE STUFF DOWN * DON'T GET STUCK ON ONE APPROACH */

Compilation message (stderr)

examination.cpp: In function 'void sol()':
examination.cpp:83:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |             for(int i=(pos1-1)/sz+1; i<=(vx.size()-1)/sz; i++)tmp+=t[i].get(pos2);
      |                                      ~^~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...