/*
example test starts
5 3
5 1 2 4 3
17
F 1
F 2
F 3
F 4
F 5
E 2 1
F 1
F 2
F 3
F 4
F 5
E 5 2
F 1
F 2
F 3
F 4
F 5
example test ends
*/
#include <bits/stdc++.h>
using namespace std;
const long long MULT = 100000000000; //TODO: MAKE IT 10^6
const int N = 250007;
const int TREE_SIZE = N<<2;
const long long INF = (1e18) + 7;
struct xorshift {
unsigned long long x,y,z,w;
xorshift(): x(1234567891011121314), y(832742389), z(77777777777777), w(380737893) {}
unsigned long long next() {
unsigned long long t=x^(x<<11);
x=y;y=z;z=w;
return w=w^(w>>19)^t^(t>>8);
}
unsigned long long next(unsigned long long a) {
return next()%a;
}
unsigned long long next(long long a, long long b) {
return a+next(b-a+1);
}
} rng;
struct treap_node {
long long key;
unsigned long long priority;
unsigned size;
treap_node *left, *right;
};
struct tree_node {
long long min,max;
tree_node(): min(INF), max(-INF) {}
tree_node(long long a, long long b): min(a), max(b) {}
};
typedef treap_node *node_ptr;
int n,q,a,b;
node_ptr root;
long long arr[N];
tree_node tree[TREE_SIZE];
tree_node merge_them(tree_node a, tree_node b) {
tree_node ans;
ans.min=min(a.min,b.min);
ans.max=max(a.max,b.max);
return ans;
}
void build_tree(int a, int b, int node) {
if(a>b) return;
if(a==b) {
tree[node]=tree_node(arr[a],arr[b]);
return;
}
build_tree(a,(a+b)>>1,node<<1);
build_tree(((a+b)>>1)+1,b,(node<<1)|1);
tree[node]=merge_them(tree[node<<1],tree[(node<<1)|1]);
}
void update_tree(int a, int b, int pos, int node, long long value) {
if(a>b || a>pos || b<pos) return;
if(a==b) {
tree[node]=tree_node(value,value);
return;
}
update_tree(a,(a+b)>>1,pos,node<<1,value);
update_tree(((a+b)>>1)+1,b,pos,(node<<1)|1,value);
tree[node]=merge_them(tree[node<<1],tree[(node<<1)|1]);
}
tree_node query_tree(int a, int b, int i, int j, int node) {
if(a>b || a>j || b<i) return tree_node();
if(a>=i && b<=j) return tree[node];
return merge_them(query_tree(a,(a+b)>>1,i,j,node<<1),query_tree(((a+b)>>1)+1,b,i,j,(node<<1)|1));
}
node_ptr new_node(long long key) {
node_ptr res=(node_ptr)malloc(sizeof(treap_node));
res->key=key;
res->priority=rng.next();
res->size=1;
res->left=NULL;
res->right=NULL;
return res;
}
unsigned get_size(node_ptr &a) {
if(a==NULL) return 0;
return a->size;
}
void update_node(node_ptr &a) {
if(a!=NULL) a->size=1+get_size(a->left)+get_size(a->right);
}
node_ptr rotate_left(node_ptr x) {
node_ptr y=x->right,t2=y->left;
x->right=t2;
y->left=x;
update_node(x);
update_node(y);
return y;
}
node_ptr rotate_right(node_ptr y) {
node_ptr x=y->left,t2=x->right;
y->left=t2;
x->right=y;
update_node(y);
update_node(x);
return x;
}
node_ptr insert(node_ptr root, long long key) {
if(root==NULL) {
return new_node(key);
}
if(key<root->key) {
root->left=insert(root->left,key);
update_node(root);
if(root->left->priority>root->priority) root=rotate_right(root);
}
else {
root->right=insert(root->right,key);
update_node(root);
if(root->right->priority>root->priority) root=rotate_left(root);
}
return root;
}
node_ptr remove_it(node_ptr root) {
if(root->left==NULL && root->right==NULL) return NULL;
if(root->left==NULL) {
root=rotate_left(root);
root->left=remove_it(root->left);
}
else if(root->right==NULL) {
root=rotate_right(root);
root->right=remove_it(root->right);
}
else {
if(root->left->priority>root->right->priority) {
root=rotate_right(root);
root->right=remove_it(root->right);
}
else {
root=rotate_left(root);
root->left=remove_it(root->left);
}
}
update_node(root);
return root;
}
node_ptr erase(node_ptr root, long long key) {
if(root->key==key) {
return remove_it(root);
}
else if(key<root->key) {
root->left=erase(root->left,key);
}
else {
root->right=erase(root->right,key);
}
update_node(root);
return root;
}
long long kth(node_ptr root, unsigned k) {
if(k<=get_size(root->left)) return kth(root->left,k);
else if(k==get_size(root->left)+1) return root->key;
else return kth(root->right,k-1-get_size(root->left));
}
void insert(long long key) {
root=insert(root,key);
}
void erase(long long key) {
root=erase(root,key);
}
long long kth(long long k) {
return kth(root,k);
}
int main() {
int i,x,y;
char type[4];
root=NULL;
scanf("%d %d", &n, &a);
for(i=1;i<=n;i++) {
scanf("%lld", &arr[i]);
arr[i]*=MULT;
insert(arr[i]);
}
build_tree(1,n,1);
scanf("%d", &q);
while(q--) {
scanf("%s", type);
if(type[0]=='E') {
scanf("%d %d", &x, &y);
long long new_value=kth(n-y+1);
if(y==1) new_value+=rng.next(1,1000000000);
else new_value+=rng.next(1,kth(n-y+2)-new_value-1);
erase(arr[x]);
arr[x]=new_value;
update_tree(1,n,x,1,arr[x]);
insert(arr[x]);
continue;
}
scanf("%d", &b);
if(b==a) {
printf("0\n");
continue;
}
if(b<a) {
long long max_value=query_tree(1,n,b,a-1,1).max;
int left=a,right=n+1,middle;
while(right-left>1) {
middle=(left+right)>>1;
if(query_tree(1,n,a+1,middle,1).max<=max_value) left=middle;
else right=middle;
}
printf("%d\n", left-b);
}
else {
long long max_value=query_tree(1,n,a+1,b,1).max;
int left=0,right=a,middle;
while(right-left>1) {
middle=(left+right)>>1;
if(query_tree(1,n,middle,a-1,1).max<=max_value) right=middle;
else left=middle;
}
printf("%d\n", b-right);
}
}
return 0;
}
Compilation message
cake.cpp: In function 'int main()':
cake.cpp:221:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &n, &a);
^
cake.cpp:223:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld", &arr[i]);
^
cake.cpp:229:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &q);
^
cake.cpp:231:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s", type);
^
cake.cpp:233:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &x, &y);
^
cake.cpp:244:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &b);
^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
19600 KB |
Output is correct |
| 2 |
Correct |
0 ms |
19600 KB |
Output is correct |
| 3 |
Correct |
3 ms |
19600 KB |
Output is correct |
| 4 |
Correct |
6 ms |
19732 KB |
Output is correct |
| 5 |
Runtime error |
16 ms |
20260 KB |
Execution killed with signal 8 (could be triggered by violating memory limits) |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
3 ms |
19996 KB |
Execution killed with signal 8 (could be triggered by violating memory limits) |
| 2 |
Runtime error |
0 ms |
20128 KB |
Execution killed with signal 8 (could be triggered by violating memory limits) |
| 3 |
Runtime error |
13 ms |
20128 KB |
Execution killed with signal 8 (could be triggered by violating memory limits) |
| 4 |
Correct |
293 ms |
43492 KB |
Output is correct |
| 5 |
Runtime error |
13 ms |
20788 KB |
Execution killed with signal 8 (could be triggered by violating memory limits) |
| 6 |
Runtime error |
6 ms |
20788 KB |
Execution killed with signal 8 (could be triggered by violating memory limits) |
| 7 |
Runtime error |
13 ms |
20788 KB |
Execution killed with signal 8 (could be triggered by violating memory limits) |
| 8 |
Correct |
326 ms |
44152 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
716 ms |
24352 KB |
Output is correct |
| 2 |
Correct |
483 ms |
24352 KB |
Output is correct |
| 3 |
Runtime error |
213 ms |
24352 KB |
Execution killed with signal 8 (could be triggered by violating memory limits) |
| 4 |
Correct |
3 ms |
19600 KB |
Output is correct |
| 5 |
Correct |
956 ms |
31348 KB |
Output is correct |
| 6 |
Correct |
1113 ms |
31348 KB |
Output is correct |
| 7 |
Runtime error |
226 ms |
31348 KB |
Execution killed with signal 8 (could be triggered by violating memory limits) |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
89 ms |
20524 KB |
Execution killed with signal 8 (could be triggered by violating memory limits) |
| 2 |
Runtime error |
0 ms |
19864 KB |
Execution killed with signal 8 (could be triggered by violating memory limits) |
| 3 |
Runtime error |
43 ms |
21976 KB |
Execution killed with signal 8 (could be triggered by violating memory limits) |
| 4 |
Runtime error |
59 ms |
22240 KB |
Execution killed with signal 8 (could be triggered by violating memory limits) |
| 5 |
Runtime error |
16 ms |
19864 KB |
Execution killed with signal 8 (could be triggered by violating memory limits) |
| 6 |
Runtime error |
59 ms |
22636 KB |
Execution killed with signal 8 (could be triggered by violating memory limits) |
| 7 |
Runtime error |
3 ms |
20128 KB |
Execution killed with signal 8 (could be triggered by violating memory limits) |
| 8 |
Runtime error |
103 ms |
24352 KB |
Execution killed with signal 8 (could be triggered by violating memory limits) |
| 9 |
Runtime error |
433 ms |
31612 KB |
Execution killed with signal 8 (could be triggered by violating memory limits) |
| 10 |
Runtime error |
36 ms |
20260 KB |
Execution killed with signal 8 (could be triggered by violating memory limits) |
| 11 |
Runtime error |
13 ms |
20524 KB |
Execution killed with signal 8 (could be triggered by violating memory limits) |
| 12 |
Runtime error |
259 ms |
28972 KB |
Execution killed with signal 8 (could be triggered by violating memory limits) |
| 13 |
Runtime error |
373 ms |
31348 KB |
Execution killed with signal 8 (could be triggered by violating memory limits) |
