Submission #1087488

#TimeUsernameProblemLanguageResultExecution timeMemory
1087488Nika533Examination (JOI19_examination)C++14
0 / 100
158 ms19284 KiB
#pragma gcc diagnostic "-std=c++1z" #include <bits/stdc++.h> #define int long long #define pb push_back #define f first #define s second #define MOD 1000000007 #define pii pair<int,int> #define all(x) (x).begin(),(x).end() #define allr(x) (x).rbegin(),(x).rend() using namespace std; const int N=1e5+5; int n,m,T,k,a[N],b[N],x[N],y[N],z[N],ans[N]; vector<int> t[N*4]; void build(int v, int tl, int tr) { // if (tl==tr) { // t[v].pb(a[tl]+b[tl]); return; // } // int mid=(tl+tr)/2; // build(v*2,tl,mid); build(v*2+1,mid+1,tr); // merge(all(t[v*2]),all(t[v*2+1]),back_inserter(t[v])); } void update(int v, int tl, int tr, int ind, int val) { // t[v].clear(); // if (tl==tr) { // t[v].pb(val); return; // } // int mid=(tl+tr)/2; // if (ind<=mid) update(v*2,tl,mid,ind,val); // else update(v*2+1,mid+1,tr,ind,val); // merge(all(t[v*2]),all(t[v*2+1]),back_inserter(t[v])); } int query(int v, int tl, int tr, int l, int r, int val) { if (tl==tr) return 0; if (l>r) return 0; if (tl==l && tr==r) { return 0; // auto it=lower_bound(all(t[v]),val); // int num=it-t[v].begin(); num=(tr-tl+1)-num; // return num; } int mid=(tl+tr)/2; return query(v*2,tl,mid,l,min(r,mid),val); return query(v*2,tl,mid,l,min(r,mid),val)+query(v*2+1,mid+1,tr,max(l,mid+1),r,val); } void test_case() { cin>>n>>m; pii ab[n+1]; for (int i=1; i<=n; i++) cin>>ab[i].f>>ab[i].s; sort(ab+1,ab+1+n); for (int i=1; i<=n; i++) { a[i]=ab[i].f; b[i]=ab[i].s; } for (int i=1; i<=m; i++) cin>>x[i]>>y[i]>>z[i]; pii bi[n+1],yi[m+1]; for (int i=1; i<=n; i++) { bi[i]={b[i],i}; } for (int i=1; i<=m; i++) { yi[i]={y[i],i}; } sort(bi+1,bi+1+n); sort(yi+1,yi+1+m); int cur=1; build(1,1,n); for (int i=1; i<=m; i++) { int ind=yi[i].s; while (cur<=n && bi[cur].f<yi[i].f) { update(1,1,n,bi[cur].s,0); cur++; } int l=1,r=n,idx=0; while (l<=r) { int mid=(l+r)/2; if (a[mid]>=x[ind]) { idx=mid; r=mid-1; } else { l=mid+1; } } ans[ind]=query(1,1,n,idx,n,z[ind]); } for (int i=1; i<=m; i++) cout<<ans[i]<<endl; } main () { ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0); T=1; while (T--) test_case(); }

Compilation message (stderr)

examination.cpp:1: warning: ignoring '#pragma gcc diagnostic' [-Wunknown-pragmas]
    1 | #pragma gcc diagnostic "-std=c++1z"
      | 
examination.cpp:84:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   84 | main () {
      | ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...