oj.uz

Submission #101558

# Submission time Handle Problem Language Result Execution time Memory
101558 2019-03-19T04:23:01 Z dwsc Cake (CEOI14_cake) C++14
0 / 100
 700 ms 23800 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,y),r->rmq(x,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 (n <= 25000){
        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--;
              	continue;
                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;
                    while (l != r){
                        int m = (l+r)/2;
                        if (root->rmq(a+1,m) > maxi){
                            r = m;
                        }
                        else l = m+1;
                    }
                    l--;
                    cout << l-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 597 ms 1152 KB Output isn't correct
2 Incorrect 385 ms 1280 KB Output isn't correct
3 Incorrect 551 ms 1280 KB Output isn't correct
4 Incorrect 364 ms 1280 KB Output isn't correct
5 Incorrect 700 ms 2788 KB Output isn't correct
6 Incorrect 637 ms 2816 KB Output isn't correct
7 Incorrect 587 ms 2816 KB Output isn't correct
8 Incorrect 397 ms 2816 KB Output isn't correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 9728 KB Output isn't correct
2 Incorrect 14 ms 9728 KB Output isn't correct
3 Incorrect 17 ms 9728 KB Output isn't correct
4 Incorrect 3 ms 384 KB Output isn't correct
5 Incorrect 35 ms 23800 KB Output isn't correct
6 Incorrect 34 ms 23800 KB Output isn't correct
7 Incorrect 43 ms 23800 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 46 ms 640 KB Output isn't correct
2 Incorrect 36 ms 768 KB Output isn't correct
3 Incorrect 10 ms 5120 KB Output isn't correct
4 Incorrect 9 ms 4992 KB Output isn't correct
5 Incorrect 97 ms 512 KB Output isn't correct
6 Incorrect 11 ms 6528 KB Output isn't correct
7 Incorrect 140 ms 1280 KB Output isn't correct
8 Incorrect 18 ms 9728 KB Output isn't correct
9 Incorrect 36 ms 23800 KB Output isn't correct
10 Incorrect 393 ms 512 KB Output isn't correct
11 Incorrect 461 ms 2304 KB Output isn't correct
12 Incorrect 29 ms 19064 KB Output isn't correct
13 Incorrect 32 ms 23800 KB Output isn't correct