oj.uz

Submission #217941

# Submission time Handle Problem Language Result Execution time Memory
217941 2020-03-31T09:36:36 Z pit4h Examination (JOI19_examination) C++14
2 / 100
 3000 ms 286888 KB 
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5+1;
const ll INF = (1LL<<31);
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.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 512 KB Output is correct
5 Correct 5 ms 512 KB Output is correct
6 Correct 5 ms 512 KB Output is correct
7 Correct 92 ms 39928 KB Output is correct
8 Correct 93 ms 39928 KB Output is correct
9 Correct 99 ms 40056 KB Output is correct
10 Correct 88 ms 31352 KB Output is correct
11 Correct 116 ms 28588 KB Output is correct
12 Correct 33 ms 18424 KB Output is correct
13 Correct 87 ms 37240 KB Output is correct
14 Correct 84 ms 37240 KB Output is correct
15 Correct 87 ms 37260 KB Output is correct
16 Correct 85 ms 25440 KB Output is correct
17 Correct 74 ms 31352 KB Output is correct
18 Correct 24 ms 18432 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3080 ms 286888 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3080 ms 286888 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 512 KB Output is correct
5 Correct 5 ms 512 KB Output is correct
6 Correct 5 ms 512 KB Output is correct
7 Correct 92 ms 39928 KB Output is correct
8 Correct 93 ms 39928 KB Output is correct
9 Correct 99 ms 40056 KB Output is correct
10 Correct 88 ms 31352 KB Output is correct
11 Correct 116 ms 28588 KB Output is correct
12 Correct 33 ms 18424 KB Output is correct
13 Correct 87 ms 37240 KB Output is correct
14 Correct 84 ms 37240 KB Output is correct
15 Correct 87 ms 37260 KB Output is correct
16 Correct 85 ms 25440 KB Output is correct
17 Correct 74 ms 31352 KB Output is correct
18 Correct 24 ms 18432 KB Output is correct
19 Execution timed out 3080 ms 286888 KB Time limit exceeded
20 Halted 0 ms 0 KB -