oj.uz

답안 #116991

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
116991 2019-06-14T11:22:11 Z JohnTitor 케이크 (CEOI14_cake) C++11
0 / 100
 2000 ms 25592 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);
                int last=0;
                FFOR(j, 0, e){
                    last=d[highest[j]];
                    d[highest[j]]++;
                }
                d[i]=last;
                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);
            }
        }
    }
}

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2050 ms 1408 KB Time limit exceeded
2 Execution timed out 2060 ms 1400 KB Time limit exceeded
3 Execution timed out 2061 ms 1492 KB Time limit exceeded
4 Incorrect 83 ms 1280 KB Output isn't correct
5 Execution timed out 2061 ms 3032 KB Time limit exceeded
6 Execution timed out 2054 ms 2972 KB Time limit exceeded
7 Execution timed out 2061 ms 2948 KB Time limit exceeded
8 Incorrect 90 ms 2936 KB Output isn't correct

Subtask #3
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 90 ms 10676 KB Output isn't correct
2 Incorrect 62 ms 10588 KB Output isn't correct
3 Incorrect 48 ms 10616 KB Output isn't correct
4 Correct 2 ms 384 KB Output is correct
5 Incorrect 137 ms 25592 KB Output isn't correct
6 Incorrect 115 ms 25464 KB Output isn't correct
7 Incorrect 70 ms 25080 KB Output isn't correct

Subtask #4
0.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2025 ms 972 KB Time limit exceeded
2 Execution timed out 2060 ms 1144 KB Time limit exceeded
3 Execution timed out 2025 ms 5552 KB Time limit exceeded
4 Execution timed out 2045 ms 5496 KB Time limit exceeded
5 Execution timed out 2056 ms 1016 KB Time limit exceeded
6 Execution timed out 2069 ms 6904 KB Time limit exceeded
7 Execution timed out 2066 ms 1400 KB Time limit exceeded
8 Execution timed out 2059 ms 10232 KB Time limit exceeded
9 Execution timed out 2071 ms 25000 KB Time limit exceeded
10 Execution timed out 2059 ms 840 KB Time limit exceeded
11 Execution timed out 2047 ms 2572 KB Time limit exceeded
12 Execution timed out 2075 ms 20188 KB Time limit exceeded
13 Execution timed out 2065 ms 25208 KB Time limit exceeded