#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];
int stk[200005], p;
void update(){
for(int i=0; sz[i]; i++){
for(int j=0; j<sz[i]; j++) stk[p++] = v[i][j];
}
reverse(stk, stk + p);
for(int i=0; p; i++){
sz[i] = min(300, p);
for(int j=0; j<sz[i]; j++){
v[i][j] = stk[p-1];
map_int[p-1] = i;
p--;
}
}
}
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];
}
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 + 1;
break;
}
}
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);
}
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
3 ms |
52888 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Halted |
0 ms |
0 KB |
- |
