Submission #197881

#	Time	Username	Problem	Language	Result	Execution time	Memory
197881		gs18081	Examination (JOI19_examination)	C++17	100 / 100	675 ms	50732 KiB

examination

#include <bits/stdc++.h>

using namespace std;

typedef pair<int,int> pi;
typedef tuple<int,int,int> ti;

const int MAXN = 101010;

struct PST{
	struct Node{
		int v,l,r;
	}tree[MAXN * 40];
	int n;
	int t;
	PST(){}
	void resize(int size){
		n = size;
		t = 1;
		tree[0].v = tree[0].l = tree[0].r = 0;
	}
	void upnode(int node){
		tree[node].v = tree[tree[node].l].v + tree[tree[node].r].v;
	}
	int update(int prevnode,int s,int e,int pos,int diff){
		if(e < pos || pos < s) return prevnode;
		if(s == e){
			int now = t++;
			tree[now].v = tree[prevnode].v + diff;
			return now;
		}
		int now = t++;
		int m = (s + e) >> 1;
		tree[now].l = update(tree[prevnode].l,s,m,pos,diff);
		tree[now].r = update(tree[prevnode].r,m + 1,e,pos,diff);
		upnode(now);
		return now;
	}
	int update(int prevroot,int pos,int diff){
		return update(prevroot,0,n-1,pos,diff);
	}
	int range(int node,int s,int e,int l,int r){
		if(e < l||r < s) return 0;
		if(l <= s && e <= r) return tree[node].v;
		int m = (s + e) >> 1;
		return range(tree[node].l,s,m,l,r) + range(tree[node].r,m+1,e,l,r);
	}
	int range(int root,int srt){
		return range(root,0,n-1,srt,n-1);
	}
};

int N,Q;
vector<int> addv;
vector<int> bv;
vector<int> addroot;
vector<int> broot;
vector<ti> vect;
PST addpst;
PST bpst;


int main(){
	scanf("%d %d",&N,&Q);
	vect.push_back(ti(-1,-1,-1));
	addroot.push_back(0);
	broot.push_back(0);
	for(int i=1;i<=N;i++){
		int a,b;
		scanf("%d %d",&a,&b);
		vect.push_back(ti(a,b,a+b));
		addv.push_back(a+b);
		bv.push_back(b);
	}
	sort(addv.begin(),addv.end());
	addv.resize(unique(addv.begin(),addv.end()) - addv.begin());
	sort(bv.begin(),bv.end());
	bv.resize(unique(bv.begin(),bv.end()) - bv.begin());
	sort(vect.begin() + 1,vect.end());
	addpst.resize(addv.size());
	bpst.resize(bv.size());
	for(int i=1;i<=N;i++){
		auto [a,b,c] = vect[i];
		b = lower_bound(bv.begin(),bv.end(),b) - bv.begin();
		c = lower_bound(addv.begin(),addv.end(),c) - addv.begin();
		vect[i] = ti(a,b,c);
		addroot.push_back(addpst.update(addroot.back() , c , 1));
		broot.push_back(bpst.update(broot.back() , b , 1));
	}
	for(int i=0;i<Q;i++){
		int a,b,c;
		int ans = 0;
		scanf("%d %d %d",&a,&b,&c);
		int srt = lower_bound(vect.begin(),vect.end(),ti(a,-1,-1)) - vect.begin();
		if(a + b < c){
			int tp = lower_bound(vect.begin(),vect.end(),ti(c - b,-1,-1)) - vect.begin() - 1;
			int addsrt = lower_bound(addv.begin(),addv.end(),c) - addv.begin();
			ans += addpst.range(addroot[tp],addsrt);
			ans -= addpst.range(addroot[srt - 1],addsrt);
			srt = tp + 1;
		}
	//	printf("ang %d\n",ans);
		int bsrt = lower_bound(bv.begin(),bv.end(),b) - bv.begin();
		ans += bpst.range(broot.back(),bsrt);
		ans -= bpst.range(broot[srt - 1],bsrt);
		printf("%d\n",ans);
	}


	return 0;
}

Compilation message (stderr)

examination.cpp: In function 'int main()':
examination.cpp:64: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:70:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&a,&b);
   ~~~~~^~~~~~~~~~~~~~~
examination.cpp:93: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