oj.uz

Submission #101569

# Submission time Handle Problem Language Result Execution time Memory
101569 2019-03-19T04:32:28 Z dwsc Cake (CEOI14_cake) C++14
7.5 / 100
 2000 ms 26632 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;
                    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 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Incorrect 2 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 689 ms 1152 KB Output is correct
2 Correct 440 ms 1280 KB Output is correct
3 Correct 712 ms 1280 KB Output is correct
4 Correct 475 ms 1408 KB Output is correct
5 Incorrect 616 ms 2688 KB Output isn't correct
6 Correct 593 ms 2816 KB Output is correct
7 Correct 664 ms 2816 KB Output is correct
8 Correct 604 ms 2816 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 524 ms 10704 KB Output isn't correct
2 Correct 459 ms 10668 KB Output is correct
3 Correct 363 ms 10740 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 653 ms 25648 KB Output is correct
6 Incorrect 572 ms 25792 KB Output isn't correct
7 Correct 458 ms 25244 KB Output is correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 137 ms 760 KB Output isn't correct
2 Correct 125 ms 888 KB Output is correct
3 Correct 287 ms 5456 KB Output is correct
4 Incorrect 288 ms 5608 KB Output isn't correct
5 Incorrect 314 ms 896 KB Output isn't correct
6 Correct 584 ms 7288 KB Output is correct
7 Correct 420 ms 1876 KB Output is correct
8 Correct 308 ms 10180 KB Output is correct
9 Execution timed out 2088 ms 26304 KB Time limit exceeded
10 Incorrect 1085 ms 1732 KB Output isn't correct
11 Incorrect 1413 ms 3872 KB Output isn't correct
12 Execution timed out 2036 ms 21580 KB Time limit exceeded
13 Execution timed out 2004 ms 26632 KB Time limit exceeded