oj.uz

답안 #49205

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
49205 2018-05-23T17:21:50 Z Benq 케이크 (CEOI14_cake) C++14
0 / 100
 742 ms 13572 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(l,r,{++z,{-1,t+r}});
    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().s+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();
    }
    
    /*for (auto a: cur) cout << a.f << " " << a.s << " | ";
    cout << "\n----\n";*/
    int l = sz(highest)-1, r = 0;
    while (l >= 0 && highest[l].f >= lo) l --;
    while (r < sz(highest) && highest[r].f <= hi) r ++;
    
    while (l != -1 || r != sz(highest)) {
        if (l == -1 || (r != sz(highest) && 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 --;
        }
    }
    /*for (auto a: cur) cout << a.f << " " << a.s << " | ";
    cout << "\n----\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) cin >> D[i];
    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?)

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Runtime error 5 ms 744 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 643 ms 1840 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 204 ms 1856 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 22 ms 1860 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Incorrect 687 ms 1964 KB Output isn't correct
5 Runtime error 11 ms 2484 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 10 ms 2484 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 10 ms 2484 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Incorrect 742 ms 2576 KB Output isn't correct

Subtask #3
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 68 ms 6592 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 57 ms 6592 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Incorrect 107 ms 6592 KB Output isn't correct
4 Correct 3 ms 6592 KB Output is correct
5 Incorrect 138 ms 10632 KB Output isn't correct
6 Runtime error 141 ms 13404 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Incorrect 102 ms 13556 KB Output isn't correct

Subtask #4
0.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 19 ms 13556 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 31 ms 13556 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 18 ms 13556 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 21 ms 13556 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 12 ms 13556 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 21 ms 13556 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 30 ms 13556 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 31 ms 13556 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 74 ms 13556 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 13 ms 13556 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 9 ms 13556 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 68 ms 13556 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 75 ms 13572 KB Execution killed with signal 11 (could be triggered by violating memory limits)