Submission #217940

#	Time	Username	Problem	Language	Result	Execution time	Memory
217940		pit4h	Examination (JOI19_examination)	C++14	2 / 100	3087 ms	247316 KiB

examination

#include<bits/stdc++.h>
#define ll int
using namespace std;
const int N = 1e5+1;
const ll INF = (1<<30);
ll n, q, s[N], t[N];
vector<int> priorities;
struct Treap {
	ll key, prior, cnt, num=1;
	Treap *l=NULL, *r=NULL;
};
int cnt(Treap* it) {
	return it? it->cnt:0;
}
void upd_cnt(Treap* it) {
	if(it) {
		it->cnt = cnt(it->l) + cnt(it->r) + it->num;
	}
}
void split(Treap* T, int key, Treap* &l, Treap* &r) {
	if(!T) {
		l = r = NULL;
		return;
	}
	if(key < T->key) {
		split(T->l, key, l, T->l);
		r = T;
	}
	else {
		split(T->r, key, T->r, r);
		l = T;
	}
	upd_cnt(T);
}
bool find(Treap* &T, int key) {
	if(!T) {
		return false;
	}
	if(T->key == key) {
		T->num ++;
		upd_cnt(T);
		return true;
	}
	else if(key < T->key) {
		bool found = find(T->l, key);
		upd_cnt(T);
		return found;
	}
	else {
		bool found = find(T->r, key);
		upd_cnt(T);
		return found;
	}
}
void insert(Treap* &T, Treap* it) {
	if(!T) {
		T = it;
		return;
	}
	if(it->prior > T->prior) {
		split(T, it->key, it->l, it->r);
		T = it;
	}
	else {
		insert(it->key < T->key? T->l:T->r, it);
	}
	upd_cnt(T);
}
int query(Treap* cur, ll x) {
	if(!cur) return 0;
	if(x == cur->key) {
		return cnt(cur) - cnt(cur->r);
	}
	if(x < cur->key) {
		return query(cur->l, x);
	}
	else {
		return query(cur->r, x) + cnt(cur) - cnt(cur->r);
	}
}
struct Node {
	Treap* treap[3] = {NULL, NULL, NULL};
	ll l, r;
	Node* ls=NULL;
	Node* rs=NULL;
	void push() {
		if(!ls) {
			ll mid = (l+r)/2;
			ls = new Node;
			rs = new Node;
			ls->l = l;
			ls->r = mid;
			rs->l = mid+1;
			rs->r=r;
		}
	}
};
Node* root = NULL;
int Query(ll l, ll r, ll x, int which_treap, Node* cur=root) {
	if(cur->l > r || cur->r < l) {
		return 0;
	}
	if(l<=cur->l && r>=cur->r) {
		ll tmp = cnt(cur->treap[which_treap]) - query(cur->treap[which_treap], x-1);
		return tmp;
	}
	cur->push();
	return Query(l, r, x, which_treap, cur->ls)+Query(l, r, x, which_treap, cur->rs); 
}
void Insert(ll x, ll y, int which_treap, Node* cur=root) {
	if(cur->l>x || cur->r<x) return;
	Treap* it = new Treap;
	it->key = y;
	it->prior = priorities.back();
	it->cnt = 1;
	if(!find(cur->treap[which_treap], y)) {
		insert(cur->treap[which_treap], it);
	}
	if(cur->l==cur->r && cur->l==x) {
		return;
	}
	cur->push();
	Insert(x, y, which_treap, cur->ls);
	Insert(x, y, which_treap, cur->rs);
}
int main() {
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>q;
	root = new Node;
	root->l = 0;
	root->r = INF-1;
	for(int i=1; i<=n; ++i) {
		priorities.push_back(i);
	}
	random_shuffle(priorities.begin(), priorities.end());
	for(int i=0; i<n; ++i) {
		cin>>s[i]>>t[i];
		Insert(s[i], t[i], 0);
		Insert(s[i], s[i]+t[i], 1);
		Insert(t[i], s[i]+t[i], 2);
		priorities.pop_back();
	}
	while(q--) {
		int x, y, z;
		cin>>x>>y>>z;
		if(z > x+y) {
			cout<<Query(x, INF-1, z, 1) - Query(0, y-1, z, 2)<<'\n';
		}
		else {
			cout<<Query(x, INF-1, y, 0)<<'\n';
		}
	}
}

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