oj.uz

Submission #25841

# Submission time Handle Problem Language Result Execution time Memory
25841 2017-06-24T09:42:47 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 = 1000000000; //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 0 ms 19600 KB Output is correct
2 Correct 0 ms 19600 KB Output is correct
3 Correct 0 ms 19600 KB Output is correct
4 Correct 6 ms 19732 KB Output is correct
5 Correct 29 ms 20260 KB Output is correct

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 476 ms 43492 KB Output isn't correct
2 Incorrect 386 ms 43492 KB Output isn't correct
3 Incorrect 556 ms 43492 KB Output isn't correct
4 Correct 293 ms 43492 KB Output is correct
5 Incorrect 633 ms 44152 KB Output isn't correct
6 Incorrect 653 ms 44152 KB Output isn't correct
7 Incorrect 509 ms 44152 KB Output isn't correct
8 Correct 316 ms 44152 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 786 ms 24352 KB Output is correct
2 Correct 526 ms 24352 KB Output is correct
3 Incorrect 473 ms 24352 KB Output isn't correct
4 Correct 6 ms 19600 KB Output is correct
5 Correct 823 ms 31348 KB Output is correct
6 Correct 846 ms 31348 KB Output is correct
7 Incorrect 679 ms 31348 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 20920 KB Output is correct
2 Incorrect 123 ms 21052 KB Output isn't correct
3 Incorrect 323 ms 23692 KB Output isn't correct
4 Correct 233 ms 23692 KB Output is correct
5 Correct 223 ms 23164 KB Output is correct
6 Incorrect 759 ms 26200 KB Output isn't correct
7 Incorrect 406 ms 24748 KB Output isn't correct
8 Incorrect 419 ms 33592 KB Output isn't correct
9 Execution timed out 2000 ms 42700 KB Execution timed out
10 Correct 829 ms 31480 KB Output is correct
11 Incorrect 1039 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