Submission #131548

#	Time	Username	Problem	Language	Result	Execution time	Memory
131548		bkinik	Examination (JOI19_examination)	C++14	0 / 100	713 ms	32628 KiB

examination

#include<bits/stdc++.h>
using namespace std;

#define mp make_pair
#define pb push_back
#define pob pop_back
#define st first
#define nd second

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;

ll n,m,k,l,q;


void test() {
	cout<<"test"<<endl;
}
int main() {
	//freopen("input","r",stdin);
	vector<pair<pll,pll> > stud;
	cin>>n>>q;
	//cout<<n<<' '<<q<<endl;	
	vector<pll> xs;
	vector<pll> ys;
	vector<pll> zs;
	
	xs.resize(n+1);
	ys.resize(n+1);
	zs.resize(n+1);
	ll xleft,yleft,zleft;
	xleft = yleft = zleft = 0;
	set<pair<pll,pll> > sstud;
	stud.resize(n+1);
	for(int i=1; i<=n; i++) {
		cin>>stud[i].nd.st>>stud[i].nd.nd;
		xs.pb(mp(stud[i].nd.st,i));
		ys.pb(mp(stud[i].nd.nd,i));
		zs.pb(mp(stud[i].nd.st + stud[i].nd.nd,i));
		stud[i].st.st = i;
		stud[i].st.nd = stud[i].nd.st + stud[i].nd.nd;
		sstud.insert(mp(mp(i,stud[i].nd.st+stud[i].nd.nd) , mp(stud[i].nd.st , stud[i].nd.nd)));
	}
	sort(xs.begin(), xs.end());
	sort(ys.begin(), ys.end());
	sort(zs.begin(), zs.end());

	vector<pll> x;
	vector<pll> y;
	vector<pll> z;
	vector<ll> cnt;
	cnt.resize(q+1);
	vector<ll> ans;
	ans.resize(q+1);
	for(int i=1;i<=q; i++) {
		cin>>k;
		x.pb(mp(k,i));
		cin>>k;
		y.pb(mp(k,i));
		cin>>k;
		z.pb(mp(k,i));	
	}

	sort(x.begin(), x.end());
	sort(y.begin(), y.end());
	sort(z.begin(), z.end());
	ll curx = 0;
	ll cury = 0;
	ll curz = 0;
	for(int i=0; i<q; i++) {
		curx = x[i].st;
		cury = y[i].st;
		curz = z[i].st;
//		cout<<curx<<' '<<cury<<' '<<curz<<endl;
		while(xs[xleft].st < curx) {
			sstud.erase(stud[xs[xleft].nd]);
			xleft++;
		}
//		cout<<sstud.size()<<' ';
		cnt[x[i].nd]++;
		if(cnt[x[i].nd] == 3) {
			ans[x[i].nd] = sstud.size();
		}


		while(ys[yleft].st < cury) {
			sstud.erase(stud[ys[yleft].nd]);
			yleft++;
		}
		cnt[y[i].nd]++;
//		cout<<sstud.size()<<' ';
		if(cnt[y[i].nd] == 3) {
			ans[y[i].nd] = sstud.size();
		}


		while(zs[zleft].st < curz) {
			sstud.erase(stud[zs[zleft].nd]);
			zleft++;
		}
		cnt[z[i].nd]++;
//		cout<<sstud.size()<<endl;
		if(cnt[z[i].nd] == 3) {
			ans[z[i].nd] = sstud.size();
		}
	}
	for(int i=1; i<=q; i++) {
		cout<<ans[i]<<endl;
	}

	return 0;
}

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