답안 #25838

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
25838	2017-06-24T09:41:50 Z	Extazy	케이크 (CEOI14_cake)	C++14	15 / 100	2000 ms	44152 KB

cake

/*
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 = 1000000; //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

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	19600 KB	Output is correct
2	Correct	3 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

#	결과	실행 시간	메모리	Grader output
1	Incorrect	473 ms	43492 KB	Output isn't correct
2	Incorrect	433 ms	43492 KB	Output isn't correct
3	Incorrect	486 ms	43492 KB	Output isn't correct
4	Correct	316 ms	43492 KB	Output is correct
5	Incorrect	586 ms	44152 KB	Output isn't correct
6	Incorrect	459 ms	44152 KB	Output isn't correct
7	Incorrect	663 ms	44152 KB	Output isn't correct
8	Correct	363 ms	44152 KB	Output is correct

Subtask #3

0.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	743 ms	24352 KB	Output is correct
2	Correct	516 ms	24352 KB	Output is correct
3	Incorrect	496 ms	24352 KB	Output isn't correct
4	Correct	6 ms	19600 KB	Output is correct
5	Correct	986 ms	31348 KB	Output is correct
6	Correct	1103 ms	31348 KB	Output is correct
7	Incorrect	746 ms	31348 KB	Output isn't correct

Subtask #4

0.0 / 50.0

#	결과	실행 시간	메모리	Grader output
1	Correct	123 ms	20920 KB	Output is correct
2	Incorrect	153 ms	21052 KB	Output isn't correct
3	Incorrect	369 ms	23692 KB	Output isn't correct
4	Correct	273 ms	23692 KB	Output is correct
5	Correct	256 ms	23164 KB	Output is correct
6	Incorrect	729 ms	26200 KB	Output isn't correct
7	Incorrect	483 ms	24748 KB	Output isn't correct
8	Incorrect	433 ms	33592 KB	Output isn't correct
9	Execution timed out	2000 ms	42700 KB	Execution timed out
10	Correct	813 ms	31480 KB	Output is correct
11	Incorrect	1276 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