oj.uz

Submission #16879

# Submission time Handle Problem Language Result Execution time Memory
16879 2015-10-24T02:35:41 Z gs14004 통로 위의 개미 (kriii3_X) C++14
30 / 85
 3000 ms 53652 KB 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <limits.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <functional>
#include <vector>
#include <numeric>
#include <deque>
#include <utility>
#include <bitset>
#include <iostream>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;

 
static char _buffer[1024];
static int _currentChar = 0;
static int _charsNumber = 0;
 
static inline int _read() {
	if (_charsNumber < 0) {
		exit(1);
	}
	if (!_charsNumber || _currentChar == _charsNumber) {
		_charsNumber = (int)fread(_buffer, sizeof(_buffer[0]), sizeof(_buffer), stdin);
		_currentChar = 0;
	}
	if (_charsNumber <= 0) {
		return -1;
	}
	return _buffer[_currentChar++];
}
 
 
static inline long long _readLong() {
	int c, s;
	lint x;
	c = _read();
	while (c <= 32) c = _read();
	x = 0;
	s = 1;
	if (c == '-') {
		s = -1;
		c = _read();
	}
	while (c > 32) {
		x *= 10;
		x += c - '0';
		c = _read();
	}
	if (s < 0) x = -x;
	return x;
}
 
static inline int _readInt() {
	int c, x, s;
	c = _read();
	while (c <= 32) c = _read();
	x = 0;
	s = 1;
	if (c == '-') {
		s = -1;
		c = _read();
	}
	while (c > 32) {
		x *= 10;
		x += c - '0';
		c = _read();
	}
	if (s < 0) x = -x;
	return x;
}
 
lint l;
int q;
   
int ants_kth[200005];
   
struct node{
	int ls, rs, v;
};

node tree[4000005];
int piv = 2;
   
void add(int pos, int ps, int pe, int p){
	tree[p].v++;
	if(ps == pe) return;
	int pm = ps + (pe - ps) / 2;
	if(pos <= pm){
		if(!tree[p].ls) tree[p].ls = ++piv;
		add(pos, ps, pm, tree[p].ls);
	}
	else{
		if(!tree[p].rs) tree[p].rs = ++piv;
		add(pos, pm + 1, pe, tree[p].rs);
	}
}
   
int sum(int s, int e, int ps, int pe, int p){
	if(s <= ps && pe <= e) return tree[p].v;
	int pm = ps + (pe - ps) / 2;
	int ret = 0;
	if(pm >= s && tree[p].ls) ret += sum(s,e,ps,pm,tree[p].ls);
	if(e >= pm + 1 && tree[p].rs) ret += sum(s,e,pm+1,pe,tree[p].rs);
	return ret;
}
	  
inline int get_sum(lint s, lint e, int r){
	if(e >= 2 * l) return tree[r].v - sum(e - 2 * l + 1, s - 1, 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 qiv = 1;
   
int get_low(lint p, lint t){
	if(p == l) return qiv-1;
	int ret = 0;
	ret += get_sum(norm(-t), norm(-t) + p, 1);
	ret += get_sum(norm(- p - t), norm(- p - t) + p - 1, 1);
	ret += get_sum(norm(t), norm(t) + p, 2);
	ret += get_sum(norm(- p + t), norm(- p + t) + p - 1, 2);
	return ret;
}
   
int v[705][705];
int sz[705];

int map_int[200005];

vector<int> stk;

void update(){
	for(int i=0; sz[i]; i++){
		for(int j=0; j<sz[i]; j++) stk.push_back(v[i][j]);
	}
	reverse(stk.begin(), stk.end());
	for(int i=0; !stk.empty(); i++){
		sz[i] = min(300, (int)stk.size());
		for(int j=0; j<sz[i]; j++){
			v[i][j] = stk.back();
			map_int[stk.back()] = i;
			stk.pop_back();
		}
	}
}

int main(){
	v[0][sz[0]++] = 200000;
	l = _readLong();
	q = _readInt();
	for(int i=0; i<q; i++){
		lint t = _readLong();
		lint p = _readLong();
		if(p == 1){
			lint pos = _readLong();
			lint dx = _readLong();
			int k = 1 + get_low(pos,t);

			int buck = 0;
			while(sz[buck] && sz[buck] < k){
				k -= sz[buck++]; // make bucket
			}

			if(buck && !sz[buck]) buck--;

			map_int[qiv] = buck;
			sz[buck]++;

			for(int i=sz[buck]-1; i>=k; i--){
				v[buck][i] = v[buck][i-1];
			}

			//printf("%d %d\n",buck, k-1);
			v[buck][k-1] = qiv++;
			if(sz[buck] >= 700) update();


			int p = norm(pos - (1ll * dx * t % (2 * l)));
			if(dx < 0) add(p,0,2*l-1,2);
			else add(p,0,2*l-1,1);
		}
		else{
			int x = _readInt();
			int pt = map_int[x];
			int u = 0;
			for(int j=0; j<pt; j++){
				u += sz[j];
			}
			for(int j=0; j<sz[pt]; j++){
				if(v[pt][j] == x){
					u += j;
					break;
				}
			}
			u++;
			//printf("[%d]\n",u);
			x = u;
			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 3 ms 52108 KB Output is correct
2 Correct 4 ms 52108 KB Output is correct
3 Correct 4 ms 52108 KB Output is correct
4 Correct 4 ms 52108 KB Output is correct
5 Correct 0 ms 52108 KB Output is correct
6 Correct 5 ms 52108 KB Output is correct
7 Correct 3 ms 52108 KB Output is correct
8 Correct 3 ms 52108 KB Output is correct
9 Correct 5 ms 52108 KB Output is correct
10 Correct 4 ms 52108 KB Output is correct
11 Correct 6 ms 52108 KB Output is correct
12 Correct 0 ms 52108 KB Output is correct
13 Correct 2 ms 52108 KB Output is correct
14 Correct 11 ms 52108 KB Output is correct
15 Correct 7 ms 52108 KB Output is correct
16 Correct 3 ms 52108 KB Output is correct
17 Correct 0 ms 52108 KB Output is correct
18 Correct 0 ms 52108 KB Output is correct
19 Correct 2 ms 52108 KB Output is correct
20 Correct 3 ms 52108 KB Output is correct
21 Correct 11 ms 52108 KB Output is correct
22 Correct 5 ms 52108 KB Output is correct
23 Correct 4 ms 52108 KB Output is correct
24 Correct 4 ms 52108 KB Output is correct

Subtask #2
0.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1225 ms 52108 KB Output is correct
2 Correct 771 ms 52500 KB Output is correct
3 Correct 1737 ms 52240 KB Output is correct
4 Correct 1497 ms 52500 KB Output is correct
5 Correct 707 ms 52884 KB Output is correct
6 Correct 748 ms 52884 KB Output is correct
7 Correct 779 ms 52884 KB Output is correct
8 Correct 860 ms 52884 KB Output is correct
9 Correct 1612 ms 53652 KB Output is correct
10 Correct 1450 ms 53652 KB Output is correct
11 Correct 1510 ms 53652 KB Output is correct
12 Execution timed out 3000 ms 52500 KB Program timed out