답안 #25827

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
25827	2017-06-24T09:11:05 Z	Extazy	케이크 (CEOI14_cake)	C++14	0 / 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+2)-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:245:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &b);
                        ^

Subtask #1

0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	19600 KB	Output is correct
2	Incorrect	0 ms	19600 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #2

0.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	563 ms	43492 KB	Output isn't correct
2	Incorrect	443 ms	43492 KB	Output isn't correct
3	Incorrect	523 ms	43492 KB	Output isn't correct
4	Correct	276 ms	43492 KB	Output is correct
5	Incorrect	776 ms	44152 KB	Output isn't correct
6	Incorrect	649 ms	44152 KB	Output isn't correct
7	Incorrect	663 ms	44152 KB	Output isn't correct
8	Correct	399 ms	44152 KB	Output is correct

Subtask #3

0.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	829 ms	24352 KB	Output isn't correct
2	Incorrect	506 ms	24352 KB	Output isn't correct
3	Incorrect	573 ms	24352 KB	Output isn't correct
4	Correct	3 ms	19600 KB	Output is correct
5	Incorrect	926 ms	31348 KB	Output isn't correct
6	Incorrect	1129 ms	31348 KB	Output isn't correct
7	Incorrect	786 ms	31348 KB	Output isn't correct

Subtask #4

0.0 / 50.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	106 ms	20920 KB	Output isn't correct
2	Incorrect	139 ms	21052 KB	Output isn't correct
3	Incorrect	366 ms	23692 KB	Output isn't correct
4	Incorrect	299 ms	23692 KB	Output isn't correct
5	Incorrect	256 ms	23164 KB	Output isn't correct
6	Incorrect	746 ms	26200 KB	Output isn't correct
7	Incorrect	446 ms	24748 KB	Output isn't correct
8	Incorrect	499 ms	33592 KB	Output isn't correct
9	Execution timed out	2000 ms	42964 KB	Execution timed out
10	Incorrect	756 ms	31480 KB	Output isn't correct
11	Incorrect	1056 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