Submission #16879

#	Time	Username	Problem	Language	Result	Execution time	Memory
16879		gs14004	통로 위의 개미 (kriii3_X)	C++14	30 / 85	3000 ms	53652 KiB

X

#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 / 30
• Subtask 2: 0 / 55