Submission #15460

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
15460	2015-07-12T08:02:30 Z	gs14004	통로 위의 개미 (kriii3_X)	C++14	30 / 85	3000 ms	9960 KB

X

#include <cstdio>
#include <vector>
#include <algorithm>
#include <deque>
#include <unordered_set>
using namespace std;
typedef long long lint;

lint l;
int q;

int ants_kth[200005];

struct node{
	node *ls, *rs;
	int v;
	node(){
		ls = rs = NULL;
		v = 0;
	}
};

void add(lint pos, lint ps, lint pe, node* p){
	p->v++;
	if(ps == pe) return;
	lint pm = (ps + pe) / 2;
	if(pos <= pm){
		if(!p->ls) p->ls = new node();
		add(pos, ps, pm, p->ls);
	}
	else{
		if(!p->rs) p->rs = new node();
		add(pos, pm + 1, pe, p->rs);
	}
}

int sum(lint s, lint e, lint ps, lint pe, node* p){
	if(e < ps || pe < s) return 0;
	if(s <= ps && pe <= e) return p->v;;
	lint pm = (ps + pe) / 2;
	int ret = 0;
	if(p->ls) ret += sum(s,e,ps,pm,p->ls);
	if(p->rs) ret += sum(s,e,pm+1,pe,p->rs);
	return ret;
}

node *root1, *root2;

inline int get_sum(lint s, lint e, node *r){
	if(e >= 2 * l){
		return sum(s, 2*l-1, 0, 2*l-1, r) + sum(0, e - 2*l, 0, 2*l-1, r);
	}
	return sum(s, e, 0, 2*l-1, r);
}

inline lint norm(lint x){
	x %= 2 * l;
	x += 2 * l;
	x %= 2 * l;
	return x;
}

	int piv = 1;

int get_low(lint p, lint t){
	if(p == l) return piv-1;
	int ret = 0;
	ret += get_sum(norm(-t), norm(-t) + p, root1);
	ret += get_sum(norm(2 * l - p - t), norm(2 * l - p - t) + p - 1, root1);
	ret += get_sum(norm(t), norm(t) + p, root2);
	ret += get_sum(norm(2 * l - p + t), norm(2 * l - p + t) + p - 1, root2);
	return ret;
}

deque<int> v[505];
unordered_set<int> s[505];

int main(){
	v[0].push_back(-1);
	root1 = new node();
	root2 = new node();
	scanf("%lld %d",&l,&q);
	for(int i=0; i<q; i++){
		lint t;
		lint p;
		scanf("%lld %lld",&t,&p);
		if(p == 1){
			lint pos, dx;
			scanf("%lld %lld",&pos, &dx);
			int k = 1 + get_low(pos,t);
			s[k/400].insert(piv);
			v[k/400].push_back(-1);
			for(int i=v[k/400].size() - 1; i > k % 400; i--){
				v[k/400][i] = v[k/400][i-1];
			}
			v[k/400][k%400] = piv;
			for(int i=k / 400; i <= piv / 400; i++){
				if(v[i].size() <= 400) break;
				if(v[i].size() > 400){
					s[i].erase(v[i].back());
					s[i+1].insert(v[i].back());
					v[i+1].push_front(v[i].back());
					v[i].pop_back();
				}
			}
			piv++;
			lint p = 1ll * pos - (1ll * dx * t % (2 * l)) + 2 * l;
			p %= (2 * l);
			p += 2 * l;
			p %= 2 * l;
			if(dx < 0) add(p,0,2*l-1,root2);
			else add(p,0,2*l-1,root1);
		}
		else{
			int x;
			scanf("%d",&x);
			for(int i=0; i<=piv/400; i++){
				if(s[i].find(x) != s[i].end()){
					for(int j=0; j<v[i].size(); j++){
						if(v[i][j] == x){
							x = i * 400 + j;
							goto t;
						}
					}
				}
			}
			t:
			int s = 0, e = l;
			while(s != e){
				int m = (s+e)/2;
				if(get_low(m,t) < x) s = m+1;
				else e = m;
			}
			printf("%d\n",s);
		}
	}
}

Subtask #1

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	3228 KB	Output is correct
2	Correct	5 ms	2832 KB	Output is correct
3	Correct	5 ms	3096 KB	Output is correct
4	Correct	5 ms	2964 KB	Output is correct
5	Correct	7 ms	3096 KB	Output is correct
6	Correct	5 ms	3096 KB	Output is correct
7	Correct	7 ms	3360 KB	Output is correct
8	Correct	8 ms	3228 KB	Output is correct
9	Correct	5 ms	3360 KB	Output is correct
10	Correct	7 ms	3360 KB	Output is correct
11	Correct	0 ms	2832 KB	Output is correct
12	Correct	4 ms	3228 KB	Output is correct
13	Correct	12 ms	2964 KB	Output is correct
14	Correct	10 ms	2964 KB	Output is correct
15	Correct	8 ms	2832 KB	Output is correct
16	Correct	3 ms	2964 KB	Output is correct
17	Correct	4 ms	2964 KB	Output is correct
18	Correct	3 ms	3096 KB	Output is correct
19	Correct	0 ms	3228 KB	Output is correct
20	Correct	0 ms	3228 KB	Output is correct
21	Correct	18 ms	2964 KB	Output is correct
22	Correct	5 ms	2832 KB	Output is correct
23	Correct	0 ms	2832 KB	Output is correct
24	Correct	6 ms	3096 KB	Output is correct

Subtask #2

0.0 / 55.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1525 ms	5472 KB	Output is correct
2	Correct	1727 ms	9960 KB	Output is correct
3	Correct	2406 ms	5336 KB	Output is correct
4	Execution timed out	3000 ms	9960 KB	Program timed out
5	Halted	0 ms	0 KB	-