oj.uz

Submission #116995

# Submission time Handle Problem Language Result Execution time Memory
116995 2019-06-14T11:33:21 Z JohnTitor Cake (CEOI14_cake) C++11
100 / 100
 536 ms 26880 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;
                FFOR(j, 0, highest.size()) if(highest[j]==i){
                    highest.erase(highest.begin()+j);
                    break;
                }
                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();
                if(i>a) tr->update(i);
                if(i<a) tl->update(i);
            }
        }
    }
}

Compilation message

cake.cpp: In function 'int main()':
cake.cpp:4:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FFOR(i, j, k) for(int i=(j); i<(k); i++)
                                       ^
cake.cpp:103:17: note: in expansion of macro 'FFOR'
                 FFOR(j, 0, highest.size()) if(highest[j]==i){
                 ^~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 7 ms 1536 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 1408 KB Output is correct
2 Correct 75 ms 1536 KB Output is correct
3 Correct 95 ms 1536 KB Output is correct
4 Correct 71 ms 1400 KB Output is correct
5 Correct 135 ms 2944 KB Output is correct
6 Correct 121 ms 3064 KB Output is correct
7 Correct 112 ms 2944 KB Output is correct
8 Correct 79 ms 2816 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 10832 KB Output is correct
2 Correct 68 ms 10592 KB Output is correct
3 Correct 45 ms 10588 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 141 ms 25436 KB Output is correct
6 Correct 115 ms 25464 KB Output is correct
7 Correct 70 ms 25208 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 896 KB Output is correct
2 Correct 22 ms 1152 KB Output is correct
3 Correct 63 ms 5624 KB Output is correct
4 Correct 57 ms 5624 KB Output is correct
5 Correct 43 ms 1272 KB Output is correct
6 Correct 116 ms 7416 KB Output is correct
7 Correct 85 ms 2040 KB Output is correct
8 Correct 87 ms 10360 KB Output is correct
9 Correct 536 ms 26880 KB Output is correct
10 Correct 130 ms 1784 KB Output is correct
11 Correct 255 ms 4072 KB Output is correct
12 Correct 516 ms 21752 KB Output is correct
13 Correct 274 ms 26724 KB Output is correct