답안 #25841

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
25841	2017-06-24T09:42:47 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 = 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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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