Submission #1087466

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087466		Nika533	Examination (JOI19_examination)	C++14	0 / 100	3047 ms	1048576 KiB

examination

#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 (l>r) return 0;
     if (tl==l && tr==r) {
          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)+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:81:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   81 | main () {
      | ^~~~

• Subtask 1: 0 / 2
• Subtask 2: 0 / 20
• Subtask 3: 0 / 21
• Subtask 4: 0 / 57