답안 #49208

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
49208 2018-05-23T18:40:07 Z Benq 케이크 (CEOI14_cake) C++14
100 / 100
919 ms 11436 KB
#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?)
# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 4 ms 376 KB Output is correct
3 Correct 3 ms 428 KB Output is correct
4 Correct 7 ms 608 KB Output is correct
5 Correct 21 ms 1024 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 443 ms 1092 KB Output is correct
2 Correct 656 ms 1168 KB Output is correct
3 Correct 766 ms 1168 KB Output is correct
4 Correct 574 ms 1168 KB Output is correct
5 Correct 591 ms 1660 KB Output is correct
6 Correct 642 ms 1660 KB Output is correct
7 Correct 919 ms 1724 KB Output is correct
8 Correct 559 ms 1724 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 81 ms 4336 KB Output is correct
2 Correct 81 ms 4336 KB Output is correct
3 Correct 59 ms 4336 KB Output is correct
4 Correct 2 ms 4336 KB Output is correct
5 Correct 149 ms 8116 KB Output is correct
6 Correct 112 ms 8164 KB Output is correct
7 Correct 104 ms 8164 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 49 ms 8164 KB Output is correct
2 Correct 59 ms 8164 KB Output is correct
3 Correct 111 ms 8164 KB Output is correct
4 Correct 106 ms 8164 KB Output is correct
5 Correct 135 ms 8164 KB Output is correct
6 Correct 162 ms 8164 KB Output is correct
7 Correct 182 ms 8164 KB Output is correct
8 Correct 281 ms 8164 KB Output is correct
9 Correct 736 ms 11324 KB Output is correct
10 Correct 444 ms 11324 KB Output is correct
11 Correct 444 ms 11324 KB Output is correct
12 Correct 752 ms 11324 KB Output is correct
13 Correct 515 ms 11436 KB Output is correct