oj.uz

Submission #101577

# Submission time Handle Problem Language Result Execution time Memory
101577 2019-03-19T04:38:18 Z dwsc Cake (CEOI14_cake) C++14
7.5 / 100
 2000 ms 26628 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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 3 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 708 ms 1280 KB Output is correct
2 Correct 496 ms 1280 KB Output is correct
3 Correct 609 ms 1280 KB Output is correct
4 Correct 453 ms 1280 KB Output is correct
5 Incorrect 611 ms 2688 KB Output isn't correct
6 Correct 584 ms 2816 KB Output is correct
7 Correct 599 ms 2816 KB Output is correct
8 Correct 442 ms 2816 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 559 ms 10780 KB Output isn't correct
2 Correct 392 ms 10712 KB Output is correct
3 Correct 375 ms 10592 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 705 ms 25520 KB Output is correct
6 Incorrect 647 ms 25560 KB Output isn't correct
7 Correct 476 ms 25212 KB Output is correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 132 ms 760 KB Output isn't correct
2 Correct 121 ms 1000 KB Output is correct
3 Correct 262 ms 5432 KB Output is correct
4 Incorrect 306 ms 5496 KB Output isn't correct
5 Incorrect 319 ms 928 KB Output isn't correct
6 Correct 614 ms 7220 KB Output is correct
7 Correct 492 ms 1924 KB Output is correct
8 Correct 335 ms 10180 KB Output is correct
9 Execution timed out 2020 ms 26204 KB Time limit exceeded
10 Incorrect 1006 ms 1772 KB Output isn't correct
11 Incorrect 1416 ms 3688 KB Output isn't correct
12 Execution timed out 2093 ms 21536 KB Time limit exceeded
13 Incorrect 1859 ms 26628 KB Output isn't correct