Submission #49207

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
49207	2018-05-23T18:39:12 Z	Benq	Cake (CEOI14_cake)	C++14	Compilation error	0 ms	0 KB

cake

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001;

int D[1<<18];

struct {
    pair<int,pi> seg[1<<19];
    pi query(int x, int ind = 1, int l = 0, int r = (1<<18)-1) {
        pi t = {seg[ind].f,seg[ind].s.f*x+seg[ind].s.s};
        if (l == r) return t;
        
        int m = (l+r)/2;
        if (x <= m) return max(t,query(x,2*ind,l,m));
        return max(t,query(x,2*ind+1,m+1,r));
    }
    void upd(int lo, int hi, pair<int,pi> v, int ind = 1, int l = 0, int r = (1<<18)-1) {
        if (r < lo || hi < l) return;
        if (lo <= l && r <= hi) {
            seg[ind] = v;
            return;
        }
        int m = (l+r)/2;
        upd(lo,hi,v,2*ind,l,m);
        upd(lo,hi,v,2*ind+1,m+1,r);
    }
} Seg;

int N, Q, a;
vpi cur, highest;
int z = 1;

bool contains(pi x, int y) {
    return min(x.f,x.s) <= y && y <= max(x.f,x.s);
}

void se(int l, int r, int& t) {
    cur.pb({l,r});
    if (l <= r) Seg.upd(l,r,{++z,{1,t-l}});
    else Seg.upd(r,l,{++z,{-1,t+l}});
    t += abs(l-r)+1;
}

void renumerate(int x, int y) {
    for (auto& a: highest) if (a.s >= y) a.s ++;
    int ind = 0; while (ind < sz(highest) && highest[ind].f < x) ind ++;
    highest.insert(highest.begin()+ind,{x,y});
    if (ind != sz(highest)-1 && highest[ind+1].f == x) {
        int t = highest[ind+1].s;
        highest.erase(highest.begin()+ind+1);
        for (auto& a: highest) if (a.s > t) a.s --;
    }
    if (sz(highest) > 10) F0R(i,sz(highest)) if (highest[i].s == 11) highest.erase(highest.begin()+i);
}

void mod(int x, int y) {
    renumerate(x,y);
    if (x == a) return;
    
    int lo = 0, hi = N-1, t = N;
    
    while (!contains(cur.back(),x)) {
        t -= abs(cur.back().f-cur.back().s)+1;
        if (cur.back().s < a) lo = cur.back().f+1;
        else hi = cur.back().f-1;
        cur.pop_back();
    }
    
    t -= abs(x-cur.back().s)+1;
    if (cur.back().s < a) {
        cur.back().s = lo = x+1;
        if (cur.back().s > cur.back().f) cur.pop_back();
    } else {
        cur.back().s = hi = x-1;
        if (cur.back().s < cur.back().f) cur.pop_back();
    }
    
    int l = sz(highest)-1, r = 0;
    while (l >= 0 && highest[l].f >= lo) l --;
    while (r < sz(highest) && highest[r].f <= hi) r ++;
    
    if (x == hi+1) {
        int LO = ((l == -1) ? 0 : highest[l].f+1);
        if (lo > LO) se(lo-1,LO,t); 
        lo = LO;
    } else if (x == lo-1) {
        int HI = ((r == sz(highest)) ? N-1 : highest[r].f-1);
        if (hi < HI) se(hi+1,HI,t);
        hi = HI;
    }
    
    while (lo > 0 && hi < N-1) {
        if (l == -1) {
            se(lo-1,0,t); lo = 0;
        } else if (r == sz(highest)) {
            se(hi+1,N-1,t); hi = N-1;
        } else if (highest[l].s < highest[r].s) {
            int HI = ((r+1 == sz(highest)) ? N-1 : highest[r+1].f-1);
            se(hi+1,HI,t);
            hi = HI; r ++;
        } else {
            int LO = ((l == 0) ? 0 : highest[l-1].f+1);
            se(lo-1,LO,t);
            lo = LO; l --;
        }
    }
    
    if (hi < N-1) se(hi+1,N-1,t);
    if (lo > 0) se(lo-1,0,t);
    
    /*for (auto a: cur) cout << a.f << " " << a.s << " | ";
    cout << "\n";*/
}

void init() {
    int l = a, r = a;
    int co = 0;
    while (r-l != N-1) {
        if (r == N-1 || (l != 0 && D[l-1] < D[r+1])) {
            l --; cur.pb({l,l});
            Seg.upd(l,l,{1,{0,++co}});
        } else {
            r ++; cur.pb({r,r});
            Seg.upd(r,r,{1,{0,++co}});
        }
    }
    F0R(i,N) if (D[i] > N-10) highest.pb({i,N+1-D[i]});
    sort(all(highest));
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> N >> a; a --;
    F0R(i,N) {
        // D[i] = i+1;
        cin >> D[i];
    }
    // random_shuffle(D,D+N);
    cin >> Q;
    
    init();
    F0R(i,Q) {
        char c; cin >> c;
        if (c == 'F') {
            int x; cin >> x;
            cout << Seg.query(x-1).s << "\n";
        } else {
            int x, y; cin >> x >> y;
            mod(x-1,y);
        }
    }
}

// read the question correctly (is y a vowel? what are the exact constraints?)
// look out for SPECIAL CASES (n=1?) and overflow (ll vs int?)

Compilation message

Compilation timeout while compiling cake