Submission #131448

#	Time	Username	Problem	Language	Result	Execution time	Memory
131448		hamzqq9	Examination (JOI19_examination)	C++14	100 / 100	528 ms	26440 KiB

examination

#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);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~

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