oj.uz

답안 #217903

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
217903 2020-03-31T08:09:59 Z pit4h Examination (JOI19_examination) C++14
0 / 100
 3000 ms 281204 KB 
#include<bits/stdc++.h>
#define ll long long
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;
	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) + 1;
	}
}
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);
}
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->l);
	}
	if(x < cur->key) {
		return query(cur->l, x);
	}
	else {
		return query(cur->r, x) + 1 + cnt(cur->l);
	}
}
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) {
		//~ cout<<"answering: "<<(cur->l)<<' '<<(cur->r)<<' '<<cnt(cur->treap[which_treap])<<'\n';
		ll tmp = cnt(cur->treap[which_treap]) - query(cur->treap[which_treap], x);
		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;
	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
0 / 2.0

# 결과 실행 시간 메모리 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 75 ms 34936 KB Output is correct
8 Correct 78 ms 35064 KB Output is correct
9 Correct 91 ms 35192 KB Output is correct
10 Incorrect 66 ms 26360 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3087 ms 281204 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3087 ms 281204 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# 결과 실행 시간 메모리 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 75 ms 34936 KB Output is correct
8 Correct 78 ms 35064 KB Output is correct
9 Correct 91 ms 35192 KB Output is correct
10 Incorrect 66 ms 26360 KB Output isn't correct
11 Halted 0 ms 0 KB -