oj.uz

Submission #101575

# Submission time Handle Problem Language Result Execution time Memory
101575 2019-03-19T04:37:37 Z dwsc Cake (CEOI14_cake) C++14
0 / 100
 2000 ms 26616 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 = a;
                        }
                        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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 592 ms 1280 KB Output isn't correct
2 Incorrect 524 ms 1280 KB Output isn't correct
3 Incorrect 559 ms 1280 KB Output isn't correct
4 Incorrect 439 ms 1280 KB Output isn't correct
5 Incorrect 610 ms 2816 KB Output isn't correct
6 Incorrect 540 ms 2816 KB Output isn't correct
7 Incorrect 565 ms 2816 KB Output isn't correct
8 Incorrect 456 ms 2816 KB Output isn't correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 506 ms 10816 KB Output isn't correct
2 Incorrect 394 ms 10812 KB Output isn't correct
3 Incorrect 400 ms 10724 KB Output isn't correct
4 Incorrect 2 ms 256 KB Output isn't correct
5 Incorrect 646 ms 25424 KB Output isn't correct
6 Incorrect 597 ms 25568 KB Output isn't correct
7 Incorrect 520 ms 25264 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 119 ms 760 KB Output isn't correct
2 Incorrect 123 ms 1132 KB Output isn't correct
3 Incorrect 290 ms 5604 KB Output isn't correct
4 Incorrect 237 ms 5496 KB Output isn't correct
5 Incorrect 345 ms 908 KB Output isn't correct
6 Incorrect 576 ms 7364 KB Output isn't correct
7 Incorrect 393 ms 2072 KB Output isn't correct
8 Incorrect 336 ms 10104 KB Output isn't correct
9 Execution timed out 2061 ms 26536 KB Time limit exceeded
10 Incorrect 1126 ms 1852 KB Output isn't correct
11 Incorrect 1284 ms 3880 KB Output isn't correct
12 Execution timed out 2096 ms 21448 KB Time limit exceeded
13 Incorrect 1990 ms 26616 KB Output isn't correct