oj.uz

Submission #101583

# Submission time Handle Problem Language Result Execution time Memory
101583 2019-03-19T04:41:27 Z dwsc Cake (CEOI14_cake) C++14
100 / 100
 1787 ms 26596 KB 
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
struct node{
    int s,e,m;
    int v;
    node *l,*r;
    node(int _s,int _e){
        s = _s;
        e = _e;
        m = (s+e)/2;
        v = 0;
        if (s != e){
            l = new node(s,m);
            r = new node(m+1,e);
        }
    }
    void up(int x,int v1){
        if (s == e){
            v = v1;
            return;
        }
        if (x <= m) l->up(x,v1);
        else r ->up(x,v1);
        v = max(l->v,r->v);
    }
    int rmq(int x,int y){
        if (s == x && e == y) return v;
        if (y <= m) return l->rmq(x,y);
        if (x > m) return r->rmq(x,y);
        return max(l->rmq(x,m),r->rmq(m+1,y));
    }
}*root;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n,a,q;
    cin >> n >>a;
    a--;
    root = new node(0,n-1);
    if (true){
        int arr[n];
        set<ii> s;
        for (int i = 0; i < n; i++){
            cin >> arr[i];
            s.insert(ii(arr[i],i));
            if (s.size() > 10) s.erase(s.begin());
            root->up(i,arr[i]);
        }
        int q;
        cin >> q;
        vector<ii> del;
        for (auto it = s.begin(); it != s.end(); ++it){
            del.push_back(*it);
            //cout << (*it).first << " " << (*it).second << "\n";
        }
        for (int i = 0; i < q; i++){
            char c;
            cin >> c;
            if (c == 'E'){
                int x,k;
                cin >> x >> k;
                x--;
                set<ii> s2;
                for (int j = del.size()-1; j >= 0; j--){
                    if (del.size()-j < k){
                        s2.insert(ii(del[j].first+1,del[j].second));
                        root->up(del[j].second,del[j].first+1);
                    }
                    else{
                        if (del[j].second != x)s2.insert(ii(del[j].first,del[j].second));
                    }
                    if (del.size()-j==k){
                        s2.insert(ii(del[j].first+1,x));
                        root->up(x,del[j].first+1);
                    }
                    if (s2.size() > 10) s2.erase(s2.begin());
                }
                del.clear();
                for (auto it = s2.begin(); it != s2.end(); ++it){
                    del.push_back(*it);
                   // cout << (*it).first << " " << (*it).second << "\n";
                }
            }
            else{
                int b;
                cin >> b;
                b--;
                if (a == b) cout << "0\n";
                else if (a < b){
                    int maxi = root->rmq(a+1,b);
                    int l = 0, r = a;
                    int ans = -1;
                    while (l != r){
                        int m = (l+r)/2;
                        if (root->rmq(m,a-1) > maxi){
                            ans = m;
                            l = m+1;
                        }
                        else r = m;
                    }
                    ans++;
                    cout << b-ans << "\n";
                }
                else{
                    int maxi = root->rmq(b,a-1);
                    int l = a+1, r = n;
                    int ans = n;
                    while (l != r){
                        int m = (l+r)/2;
                        if (root->rmq(a+1,m) > maxi){
                            r = m;
                            ans = m;
                        }
                        else l = m+1;
                    }
                    ans--;
                    cout << ans-b << "\n";
                }
            }
        }
    }
    else{

    }
}

Compilation message

cake.cpp: In function 'int main()':
cake.cpp:66:38: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                     if (del.size()-j < k){
                         ~~~~~~~~~~~~~^~~
cake.cpp:73:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                     if (del.size()-j==k){
                         ~~~~~~~~~~~~^~~
cake.cpp:37:13: warning: unused variable 'q' [-Wunused-variable]
     int n,a,q;
             ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 9 ms 512 KB Output is correct
5 Correct 32 ms 1408 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 675 ms 1280 KB Output is correct
2 Correct 501 ms 1280 KB Output is correct
3 Correct 478 ms 1280 KB Output is correct
4 Correct 496 ms 1528 KB Output is correct
5 Correct 646 ms 2816 KB Output is correct
6 Correct 576 ms 2816 KB Output is correct
7 Correct 546 ms 2936 KB Output is correct
8 Correct 502 ms 2936 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 354 ms 10748 KB Output is correct
2 Correct 215 ms 10604 KB Output is correct
3 Correct 193 ms 10616 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 409 ms 25592 KB Output is correct
6 Correct 397 ms 25504 KB Output is correct
7 Correct 288 ms 25208 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 860 KB Output is correct
2 Correct 66 ms 988 KB Output is correct
3 Correct 180 ms 5496 KB Output is correct
4 Correct 204 ms 5496 KB Output is correct
5 Correct 212 ms 912 KB Output is correct
6 Correct 433 ms 7288 KB Output is correct
7 Correct 294 ms 1772 KB Output is correct
8 Correct 304 ms 10104 KB Output is correct
9 Correct 1752 ms 26432 KB Output is correct
10 Correct 732 ms 1656 KB Output is correct
11 Correct 882 ms 3604 KB Output is correct
12 Correct 1787 ms 21608 KB Output is correct
13 Correct 1388 ms 26596 KB Output is correct