Submission #131448

#TimeUsernameProblemLanguageResultExecution timeMemory
131448hamzqq9Examination (JOI19_examination)C++14
100 / 100
528 ms26440 KiB
#include<bits/stdc++.h> #define st first #define nd second #define pb push_back #define ppb pop_back #define ii pair<int,int> #define orta ((bas+son)>>1) #define sz(x) ((int)x.size()) #define all(x) x.begin(),x.end() #define inf 1000000000 #define N 300005 using namespace std; #define fpos bos struct query { int w,val,id,sg; }; struct seg { int s[N<<2]; void up(int node,int bas,int son,int x) { if(bas==x && son==x) { s[node]++; return ; } if(orta>=x) up(node<<1,bas,orta,x); else up(node<<1|1,orta+1,son,x); s[node]=s[node<<1]+s[node<<1|1]; } int get(int node,int bas,int son,int x,int y) { if(bas>y || son<x || x>y) return 0; if(bas>=x && son<=y) return s[node]; return get(node<<1,bas,orta,x,y)+get(node<<1|1,orta+1,son,x,y); } } s[2]; int n,q; int a2[2][N],cnt[2],ans[N]; vector<query> qu[N]; ii ar[N]; int fpos(int w,int val) { int bas=1,son=cnt[w]; while(bas<=son) { if(a2[w][orta]<val) bas=orta+1; else son=orta-1; } return bas; } void cmp() { map<int,int> mp[2]; for(int i=1;i<=n;i++) { mp[0][ar[i].nd]=1; mp[1][ar[i].st+ar[i].nd]=1; } for(int i=0;i<2;i++) { for(auto& x:mp[i]) { a2[i][++cnt[i]]=x.st; } } } int main() { scanf("%d %d",&n,&q); for(int i=1;i<=n;i++) { int x,y; scanf("%d %d",&x,&y); ar[i]={x,y}; } sort(ar+1,ar+1+n,[](ii a,ii b){return a.st>b.st;}); cmp(); for(int i=1;i<=q;i++) { int a,b,c; scanf("%d %d %d",&a,&b,&c); int bas=1,son=n; while(bas<=son) { if(ar[orta].st<=c-b) son=orta-1; else bas=orta+1; } int ul=bas; bas=1,son=n; while(bas<=son) { if(ar[orta].st<a) son=orta-1; else bas=orta+1; } if(ul<=son) { qu[ul-1].pb({1,c,i,-1}); qu[son].pb({1,c,i,1}); qu[ul-1].pb({0,b,i,1}); } else { qu[son].pb({0,b,i,1}); } } for(int i=1;i<=n;i++) { s[0].up(1,1,cnt[0],fpos(0,ar[i].nd)); s[1].up(1,1,cnt[1],fpos(1,ar[i].st+ar[i].nd)); for(auto x:qu[i]) { ans[x.id]+=x.sg*s[x.w].get(1,1,cnt[x.w],fpos(x.w,x.val),cnt[x.w]); } } for(int i=1;i<=q;i++) printf("%d\n",ans[i]); }

Compilation message (stderr)

examination.cpp: In function 'int main()':
examination.cpp:98:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&q);
  ~~~~~^~~~~~~~~~~~~~~
examination.cpp:104:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&x,&y);
   ~~~~~^~~~~~~~~~~~~~~
examination.cpp:118:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d",&a,&b,&c);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...