oj.uz

Submission #116994

# Submission time Handle Problem Language Result Execution time Memory
116994 2019-06-14T11:30:48 Z JohnTitor Cake (CEOI14_cake) C++11
0 / 100
 560 ms 30968 KB 
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, j, k) for(int i=(j); i<=(k); i++)
#define FFOR(i, j, k) for(int i=(j); i<(k); i++)
#define DFOR(i, j, k) for(int i=(j); i>=(k); i--)
#define bug(x) cerr<<#x<<" = "<<(x)<<'\n'
#define pb push_back
#define mp make_pair
#define bit(s, i) (((s)>>(i))&1LL)
#define mask(i) ((1LL<<(i)))
#define builtin_popcount __builtin_popcountll
#define __builtin_popcount __builtin_popcountll
using ll=long long; using ld=long double;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); const ld pi=acos(0)*2;
template <typename T> inline void read(T &x){char c; bool nega=0; while((!isdigit(c=getchar()))&&(c!='-')); if(c=='-'){nega=1; c=getchar();} x=c-48; while(isdigit(c=getchar())) x=x*10+c-48; if(nega) x=-x;}
template <typename T> inline void writep(T x){if(x>9) writep(x/10); putchar(x%10+48);}
template <typename T> inline void write(T x){if(x<0){ putchar('-'); x=-x;} writep(x);}
template <typename T> inline void writeln(T x){write(x); putchar('\n');}
#define taskname "Cake"
int n, a;
int d[250001];
vector <int> highest;
class segment_tree{
public:
    using pointer=segment_tree*;
    pointer left, right;
    int l, r, m;
    int b;
    segment_tree(int l, int r){
        this->l=l;
        this->r=r;
        m=(l+r)/2;
        if(l==r) b=l;
        else{
            left=new segment_tree(l, m);
            right=new segment_tree(m+1, r);
            if(d[left->b]>d[right->b]) b=left->b;
            else b=right->b;
        }
    }
    int get_max(int u, int v){
        if(l>v||r<u) return 0;
        if(u<=l&&v>=r) return d[b];
        else return max(left->get_max(u, v), right->get_max(u, v));
    }
    int find_last_from_left(int maxd){
        if(l==r) return (d[l]<=maxd)?l:(l-1);
        if(d[left->b]>maxd) return left->find_last_from_left(maxd);
        else return right->find_last_from_left(maxd);
    }
    int find_last_from_right(int maxd){
        if(l==r) return (d[r]<=maxd)?r:(r+1);
        if(d[right->b]>maxd) return right->find_last_from_right(maxd);
        else return left->find_last_from_right(maxd);
    }
    void update(int u){
        if(l==r) return;
        else{
            if(m>=u) left->update(u);
            else right->update(u);
            if(d[left->b]>d[right->b]) b=left->b;
            else b=right->b;
        }
    }
};
segment_tree::pointer tl, tr;
int main(){
    #ifdef Aria
        if(fopen(taskname".in", "r"))
            freopen(taskname".in", "r", stdin);
    #endif // Aria
    read(n);
    read(a);
    FOR(i, 1, n){
        read(d[i]);
        if(d[i]>n-10) highest.pb(i);
    }
    sort(highest.begin(), highest.end(), [](int a, int b){
        return d[a]>d[b];
    });
    if(a!=1&&a!=n){
        tl=new segment_tree(1, a-1);
        tr=new segment_tree(a+1, n);
    }
    {
        int q;
        char c;
        int i, e;
        read(q);
        while(q--){
            while(!isalpha(c=getchar()));
            if(c=='F'){
                read(i);
                if(i==a) writeln(0);
                else if(a==1||a==n) writeln(abs(a-i));
                else if(i>a) writeln(i-tl->find_last_from_right(tr->get_max(a+1, i)));
                else writeln(tr->find_last_from_left(tl->get_max(i, a-1))-i);
            }
            else{
                read(i);
                read(e);
                if(a==1||a==n) continue;
                for(auto &x: highest) if(x==i){
                    swap(x, highest.back());
                    highest.pop_back();
                    break;
                }
//                highest.pb(i);
                FFOR(j, 1, e) d[highest[j-1]]++;
                d[i]=d[highest[e-1]]+1;
                highest.insert(highest.begin()+e-1, i);
                while(highest.size()>10) highest.pop_back();
//                sort(highest.begin(), highest.end(), [](int a, int b){
//                    return d[a]>d[b];
//                });
                if(i>a) tr->update(i);
                if(i<a) tl->update(i);
//                FOR(i, 1, n) cerr<<d[i]<<" \n"[i==n];
            }
        }
    }
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Incorrect 4 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 103 ms 5244 KB Output isn't correct
2 Correct 70 ms 4344 KB Output is correct
3 Correct 91 ms 5112 KB Output is correct
4 Correct 65 ms 1280 KB Output is correct
5 Incorrect 129 ms 6912 KB Output isn't correct
6 Correct 117 ms 7088 KB Output is correct
7 Correct 110 ms 7148 KB Output is correct
8 Correct 76 ms 2816 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 10656 KB Output is correct
2 Correct 66 ms 10532 KB Output is correct
3 Correct 46 ms 10492 KB Output is correct
4 Incorrect 2 ms 256 KB Output isn't correct
5 Correct 141 ms 25464 KB Output is correct
6 Incorrect 111 ms 25436 KB Output isn't correct
7 Correct 71 ms 25336 KB Output is correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 768 KB Output isn't correct
2 Correct 33 ms 980 KB Output is correct
3 Correct 60 ms 5724 KB Output is correct
4 Correct 59 ms 5700 KB Output is correct
5 Incorrect 44 ms 1400 KB Output isn't correct
6 Correct 107 ms 8208 KB Output is correct
7 Correct 71 ms 3064 KB Output is correct
8 Correct 86 ms 11584 KB Output is correct
9 Incorrect 560 ms 30968 KB Output isn't correct
10 Incorrect 130 ms 4728 KB Output isn't correct
11 Incorrect 218 ms 7456 KB Output isn't correct
12 Correct 507 ms 25888 KB Output is correct
13 Incorrect 275 ms 30712 KB Output isn't correct