Submission #885765

#	Time	Username	Problem	Language	Result	Execution time	Memory
885765		dsyz	Examination (JOI19_examination)	C++17	100 / 100	622 ms	271724 KiB

examination

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (1000005)
struct node {
	ll s,e,m,v;
	node *l, *r;
	node(ll _s,ll _e){
		s = _s;
		e = _e;
		m = (s + e) / 2;
		v = 0;
		if(s != e){
			l = new node(s,m);
			r = new node(m + 1,e);
		}
	}
	void update(ll x,ll nval){
		if(s == e){
			v += nval;
			return;
		}else{
			if(x > m) r->update(x,nval);
			else l->update(x,nval);
			v = l->v + r->v;
		}
	}
	ll query(ll x,ll y){
		if(s == x && e == y){
			return v;
		}else{
			if(x > m) return r->query(x,y);
			else if(y <= m) return l->query(x,y);
			else return l->query(x,m) + r->query(m+1,y);
		}
	}
} *Sroot, *Troot;
int main() {
	ios_base::sync_with_stdio(false);cin.tie(0);
	ll N,Q;
	cin>>N>>Q;
	Sroot = new node(0,MAXN - 1);
	Troot = new node(0,MAXN - 1);
	pair<pair<ll,ll>,pair<ll,ll> > queries[Q];
	pair<pair<ll,ll>,pair<ll,ll> > students[N];
	vector<ll> d;
	for(ll i = 0;i < N;i++){
		cin>>students[i].second.first>>students[i].second.second;
		students[i].first.first = students[i].second.first + students[i].second.second;
		students[i].first.second = i;
		d.push_back(students[i].first.first);
		d.push_back(students[i].second.first);
		d.push_back(students[i].second.second);
	}
	for(ll i = 0;i < Q;i++){
		cin>>queries[i].second.first>>queries[i].second.second>>queries[i].first.first;
		queries[i].first.first = max(queries[i].first.first,queries[i].second.first + queries[i].second.second);
		queries[i].first.second = i;
		d.push_back(queries[i].first.first);
		d.push_back(queries[i].second.first);
		d.push_back(queries[i].second.second);
	}
	sort(d.begin(),d.end());
	d.resize(unique(d.begin(),d.end()) - d.begin());
	for(ll i = 0;i < N;i++){
		students[i].first.first = lower_bound(d.begin(),d.end(),students[i].first.first) - d.begin();
		students[i].second.first = lower_bound(d.begin(),d.end(),students[i].second.first) - d.begin();
		students[i].second.second = lower_bound(d.begin(),d.end(),students[i].second.second) - d.begin();
	}
	for(ll i = 0;i < Q;i++){
		queries[i].first.first = lower_bound(d.begin(),d.end(),queries[i].first.first) - d.begin();
		queries[i].second.first = lower_bound(d.begin(),d.end(),queries[i].second.first) - d.begin();
		queries[i].second.second = lower_bound(d.begin(),d.end(),queries[i].second.second) - d.begin();
	}
	sort(students,students + N,greater<pair<pair<ll,ll>,pair<ll,ll> > >());
	sort(queries,queries + Q,greater<pair<pair<ll,ll>,pair<ll,ll> > >());
	ll ptr = -1;
	ll Qu[Q];
	for(ll q = 0;q < Q;q++){
		ll Z = queries[q].first.first;
		ll X = queries[q].second.first; //S <= X
		ll Y = queries[q].second.second; //T <= Y
		while(ptr + 1 < N && students[ptr + 1].first.first >= Z){
			ptr++;
			Sroot -> update(students[ptr].second.first,1);
			Troot -> update(students[ptr].second.second,1);
		}
		ll ans = ptr + 1;
		if(X >= 1) ans -= Sroot -> query(0,X - 1);
		if(Y >= 1) ans -= Troot -> query(0,Y - 1);
		Qu[queries[q].first.second] = ans;
	}
	for(ll q = 0;q < Q;q++){
		cout<<Qu[q]<<'\n';
	}
}

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