oj.uz

Submission #101567

# Submission time Handle Problem Language Result Execution time Memory
101567 2019-03-19T04:31:11 Z dwsc Cake (CEOI14_cake) C++14
7.5 / 100
 1378 ms 23808 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 (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--;
                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 Correct 2 ms 256 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Incorrect 4 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
7.5 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 581 ms 1152 KB Output is correct
2 Correct 447 ms 1280 KB Output is correct
3 Correct 603 ms 1280 KB Output is correct
4 Correct 428 ms 1280 KB Output is correct
5 Incorrect 866 ms 2688 KB Output isn't correct
6 Correct 586 ms 2816 KB Output is correct
7 Correct 625 ms 2816 KB Output is correct
8 Correct 416 ms 2816 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 49 ms 9720 KB Output isn't correct
2 Incorrect 15 ms 9728 KB Output isn't correct
3 Incorrect 16 ms 9728 KB Output isn't correct
4 Correct 3 ms 384 KB Output is correct
5 Incorrect 43 ms 23800 KB Output isn't correct
6 Incorrect 33 ms 23800 KB Output isn't correct
7 Incorrect 37 ms 23800 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 115 ms 724 KB Output isn't correct
2 Correct 120 ms 1060 KB Output is correct
3 Incorrect 13 ms 5020 KB Output isn't correct
4 Incorrect 8 ms 4992 KB Output isn't correct
5 Incorrect 341 ms 908 KB Output isn't correct
6 Incorrect 13 ms 6528 KB Output isn't correct
7 Correct 448 ms 1920 KB Output is correct
8 Incorrect 19 ms 9856 KB Output isn't correct
9 Incorrect 38 ms 23800 KB Output isn't correct
10 Incorrect 1010 ms 1728 KB Output isn't correct
11 Incorrect 1378 ms 3648 KB Output isn't correct
12 Incorrect 28 ms 19064 KB Output isn't correct
13 Incorrect 32 ms 23808 KB Output isn't correct