oj.uz

Submission #25842

# Submission time Handle Problem Language Result Execution time Memory
25842 2017-06-24T09:43:26 Z Extazy Cake (CEOI14_cake) C++14
15 / 100
 2000 ms 44152 KB 
/*
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 = 1000000000000; //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);*/
            long long new_value=((y==1) ? kth(n)+MULT : (kth(n-y+1)+kth(n-y+2))/2);
            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:245:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &b);
                        ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 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 9 ms 19732 KB Output is correct
5 Correct 33 ms 20260 KB Output is correct

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 459 ms 43492 KB Output isn't correct
2 Incorrect 396 ms 43492 KB Output isn't correct
3 Incorrect 446 ms 43492 KB Output isn't correct
4 Correct 279 ms 43492 KB Output is correct
5 Incorrect 616 ms 44152 KB Output isn't correct
6 Incorrect 576 ms 44152 KB Output isn't correct
7 Incorrect 536 ms 44152 KB Output isn't correct
8 Correct 319 ms 44152 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 636 ms 24352 KB Output is correct
2 Correct 456 ms 24352 KB Output is correct
3 Incorrect 496 ms 24352 KB Output isn't correct
4 Correct 0 ms 19600 KB Output is correct
5 Correct 993 ms 31348 KB Output is correct
6 Correct 1053 ms 31348 KB Output is correct
7 Incorrect 689 ms 31348 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 20920 KB Output is correct
2 Incorrect 136 ms 21052 KB Output isn't correct
3 Incorrect 333 ms 23692 KB Output isn't correct
4 Correct 286 ms 23692 KB Output is correct
5 Correct 269 ms 23164 KB Output is correct
6 Incorrect 669 ms 26200 KB Output isn't correct
7 Incorrect 393 ms 24748 KB Output isn't correct
8 Incorrect 399 ms 33592 KB Output isn't correct
9 Execution timed out 2000 ms 42964 KB Execution timed out
10 Correct 859 ms 31480 KB Output is correct
11 Incorrect 1213 ms 32272 KB Output isn't correct
12 Execution timed out 2000 ms 40720 KB Execution timed out
13 Execution timed out 2000 ms 43096 KB Execution timed out