oj.uz

Submission #25712

# Submission time Handle Problem Language Result Execution time Memory
25712 2017-06-23T19:01:09 Z gs14004 Cake (CEOI14_cake) C++11
100 / 100
 706 ms 13472 KB 
#include <cstdio>
#include <stack>
#include <utility>
#include <set>
#include <algorithm>
using namespace std;
typedef pair<int,int> pi;

int n,p,q;
int d[250005];
pi a[250005];
stack<pi> st;

struct tree1{
    int tree[530000], lim;
    void init(){
        for(lim = 1; lim <= p; lim <<= 1);
        for(int i=1; i<p; i++){
            tree[i+lim] = i;
        }
        for(int i=lim; i; i--){
            if(d[tree[2*i]] < d[tree[2*i+1]]){
                tree[i] = tree[2*i+1];
            }
            else tree[i] = tree[2*i];
        }
    }
    void upd(int p){
        p += lim;
        while(p > 1){
            p >>= 1;
            if(d[tree[2*p]] < d[tree[2*p+1]]){
                tree[p] = tree[2*p+1];
            }
            else tree[p] = tree[2*p];
        }
    }
    int low(int pos){
        int p = 1;
        while(p < lim){
            if(d[tree[2*p+1]] > d[pos]){
                p = 2*p+1;
            }
            else p = 2*p;
        }
        return tree[p];
    }
    int q(int s, int e){
        int ret = 0;
        s += lim;
        e += lim;
        while(s < e){
            if(s%2 == 1){
                if(d[tree[s]] > d[ret]){
                    ret = tree[s];
                }
                s++;
            }
            if(e%2 == 0){
                if(d[tree[e]] > d[ret]){
                    ret = tree[e];
                }
                e--;
            }
            s >>= 1;
            e >>= 1;
        }
        if(s == e && d[tree[s]] > d[ret]) ret = tree[s];
        return ret;
    }
}tree1;

struct tree2{
    int tree[530000], lim;
    void init(){
        for(lim = 1; lim <= n - p; lim <<= 1);
        for(int i=1; i<=n-p; i++){
            tree[i+lim] = i + p;
        }
        for(int i=lim; i; i--){
            if(d[tree[2*i]] < d[tree[2*i+1]]){
                tree[i] = tree[2*i+1];
            }
            else tree[i] = tree[2*i];
        }
    }
    void upd(int p){
        p -= ::p;
        p += lim;
        while(p > 1){
            p >>= 1;
            if(d[tree[2*p]] < d[tree[2*p+1]]){
                tree[p] = tree[2*p+1];
            }
            else tree[p] = tree[2*p];
        }
    }
    int low(int pos){
        int p = 1;
        while(p < lim){
            if(d[tree[2*p]] > d[pos]){
                p = 2*p;
            }
            else p = 2*p+1;
        }
        return tree[p];
    }
    int q(int s, int e){
        int ret = 0;
        s -= p;
        e -= p;
        s += lim;
        e += lim;
        while(s < e){
            if(s%2 == 1){
                if(d[tree[s]] > d[ret]){
                    ret = tree[s];
                }
                s++;
            }
            if(e%2 == 0){
                if(d[tree[e]] > d[ret]){
                    ret = tree[e];
                }
                e--;
            }
            s >>= 1;
            e >>= 1;
        }
        if(s == e && d[tree[s]] > d[ret]) ret = tree[s];
        return ret;
    }
}tree2;

int count(int t){
    if(t == p) return 0;
    if(t < p){
        int pos = tree1.q(t,p-1);
        if(d[tree2.q(p+1,n)] < d[pos]) return n - t;
        return tree2.low(pos) - t - 1;
    }
    else{
        int pos = tree2.q(p+1,t);
        if(d[tree1.q(1,p-1)] < d[pos]) return t - 1;
        int cnt = t  - tree1.low(pos) - 1;
        return cnt;
    }
}

int main(){
    scanf("%d %d",&n,&p);
    for (int i=1; i<=n; i++) {
        scanf("%d",&d[i]);
        a[i] = pi(d[i],i);
    }
    scanf("%d",&q);
    sort(a+1,a+n+1);
    for (int i=1; i<=n; i++) {
        st.push(a[i]);
    }
    tree1.init();
    tree2.init();
    for (int i=0; i<q; i++) {
        char str[3];
        scanf("%s",str);
        if(str[0] == 'E'){
            int p,q;
            scanf("%d %d",&p,&q);
            stack<pi> st2;
            set<int> s;
            for (int j=0; j<q-1; j++) {
                pi t = st.top();
                st.pop();
                if(s.find(t.second) != s.end()){
                    j--;
                    continue;
                }
                s.insert(t.second);
                d[t.second]++;
                t.first++;
                st2.push(t);
            }
            if(st.empty()) d[p] = 1;
            else d[p] = st.top().first+1;
            st.push(pi(d[p],p));
            while (!st2.empty()) {
                st.push(st2.top());
                st2.pop();
            }
            if(p < ::p) tree1.upd(p);
            else tree2.upd(p);
        }
        else if(str[0] == 'F'){
            int t;
            scanf("%d",&t);
            printf("%d\n",count(t));
        }
    }
}

Compilation message

cake.cpp: In function 'int main()':
cake.cpp:151:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&n,&p);
                         ^
cake.cpp:153:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&d[i]);
                          ^
cake.cpp:156:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&q);
                   ^
cake.cpp:165:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s",str);
                        ^
cake.cpp:168:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d %d",&p,&q);
                                 ^
cake.cpp:195:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&t);
                           ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 9008 KB Output is correct
2 Correct 0 ms 9008 KB Output is correct
3 Correct 0 ms 9008 KB Output is correct
4 Correct 0 ms 9008 KB Output is correct
5 Correct 13 ms 9140 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 589 ms 11104 KB Output is correct
2 Correct 446 ms 13316 KB Output is correct
3 Correct 429 ms 13316 KB Output is correct
4 Correct 323 ms 13340 KB Output is correct
5 Correct 619 ms 11232 KB Output is correct
6 Correct 533 ms 10812 KB Output is correct
7 Correct 466 ms 13444 KB Output is correct
8 Correct 353 ms 13472 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 9800 KB Output is correct
2 Correct 96 ms 9800 KB Output is correct
3 Correct 73 ms 9800 KB Output is correct
4 Correct 0 ms 9008 KB Output is correct
5 Correct 173 ms 11120 KB Output is correct
6 Correct 149 ms 11120 KB Output is correct
7 Correct 106 ms 11120 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 9268 KB Output is correct
2 Correct 43 ms 9268 KB Output is correct
3 Correct 83 ms 9792 KB Output is correct
4 Correct 103 ms 9792 KB Output is correct
5 Correct 133 ms 9652 KB Output is correct
6 Correct 173 ms 10180 KB Output is correct
7 Correct 139 ms 9912 KB Output is correct
8 Correct 186 ms 11488 KB Output is correct
9 Correct 696 ms 13208 KB Output is correct
10 Correct 409 ms 11104 KB Output is correct
11 Correct 446 ms 11232 KB Output is correct
12 Correct 706 ms 12808 KB Output is correct
13 Correct 549 ms 12820 KB Output is correct