답안 #101557

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
101557 2019-03-19T04:21:34 Z dwsc 케이크 (CEOI14_cake) C++14
0 / 100
36 ms 23864 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--;
                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;
             ^
# 결과 실행 시간 메모리 Grader output
1 Runtime error 5 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 13 ms 2304 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 9 ms 2432 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 11 ms 2560 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 9 ms 2560 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 24 ms 5240 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 18 ms 5468 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 18 ms 5376 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 18 ms 5376 KB Execution killed with signal 11 (could be triggered by violating memory limits)
# 결과 실행 시간 메모리 Grader output
1 Incorrect 14 ms 9728 KB Output isn't correct
2 Incorrect 15 ms 9728 KB Output isn't correct
3 Incorrect 15 ms 9728 KB Output isn't correct
4 Runtime error 3 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Incorrect 36 ms 23800 KB Output isn't correct
6 Incorrect 34 ms 23808 KB Output isn't correct
7 Incorrect 33 ms 23864 KB Output isn't correct
# 결과 실행 시간 메모리 Grader output
1 Runtime error 5 ms 1152 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 7 ms 1508 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Incorrect 9 ms 5120 KB Output isn't correct
4 Incorrect 8 ms 4992 KB Output isn't correct
5 Runtime error 5 ms 896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Incorrect 11 ms 6528 KB Output isn't correct
7 Runtime error 10 ms 2560 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Incorrect 18 ms 9728 KB Output isn't correct
9 Incorrect 30 ms 23800 KB Output isn't correct
10 Runtime error 4 ms 896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 12 ms 4352 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Incorrect 26 ms 19200 KB Output isn't correct
13 Incorrect 33 ms 23800 KB Output isn't correct