oj.uz

Submission #101582

# Submission time Handle Problem Language Result Execution time Memory
101582 2019-03-19T04:39:50 Z dwsc Cake (CEOI14_cake) C++14
83.3333 / 100
 2000 ms 26604 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);
    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:65:38: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                     if (del.size()-j < k){
                         ~~~~~~~~~~~~~^~~
cake.cpp:72:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                     if (del.size()-j==k){
                         ~~~~~~~~~~~~^~~
cake.cpp:36: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 2 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 12 ms 384 KB Output is correct
5 Correct 32 ms 1280 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 629 ms 1280 KB Output is correct
2 Correct 472 ms 1280 KB Output is correct
3 Correct 649 ms 1280 KB Output is correct
4 Correct 427 ms 1280 KB Output is correct
5 Correct 693 ms 2688 KB Output is correct
6 Correct 592 ms 2816 KB Output is correct
7 Correct 597 ms 2816 KB Output is correct
8 Correct 473 ms 2816 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 479 ms 10688 KB Output is correct
2 Correct 433 ms 10568 KB Output is correct
3 Correct 356 ms 10724 KB Output is correct
4 Correct 3 ms 256 KB Output is correct
5 Correct 593 ms 25720 KB Output is correct
6 Correct 567 ms 25576 KB Output is correct
7 Correct 451 ms 25236 KB Output is correct

Subtask #4
33.333333 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 832 KB Output is correct
2 Correct 108 ms 888 KB Output is correct
3 Correct 256 ms 5444 KB Output is correct
4 Correct 288 ms 5508 KB Output is correct
5 Correct 318 ms 1036 KB Output is correct
6 Correct 585 ms 7356 KB Output is correct
7 Correct 422 ms 1936 KB Output is correct
8 Correct 327 ms 10116 KB Output is correct
9 Execution timed out 2037 ms 26068 KB Time limit exceeded
10 Correct 1041 ms 1964 KB Output is correct
11 Correct 1417 ms 3816 KB Output is correct
12 Execution timed out 2045 ms 21436 KB Time limit exceeded
13 Correct 1916 ms 26604 KB Output is correct