oj.uz

답안 #101431

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
101431 2019-03-19T01:51:24 Z lyc 케이크 (CEOI14_cake) C++14
0 / 100
 1732 ms 152684 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> ii;
#define fi first
#define sc second
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(), (x).end()

struct node {
    int s, e, m; vector<int> v;
    node *l, *r;
    node(int _s, int _e): s(_s), e(_e), m((_s+_e)/2) {
        if (s != e) {
            l = new node(s, m);
            r = new node(m+1, e);
        }
    }

    void def(int i, int x) {
        if (s == e) { v.clear(); v.push_back(x); }
        else if (i <= m) l->def(i, x);
        else r->def(i, x);
    }

    void build() {
        if (s == e) return;
        l->build();
        r->build();
        for (int i = 0, j = 0; i < SZ(l->v) || j < SZ(r->v);) {
            if (i < SZ(l->v) && (j == SZ(r->v) || l->v[i] <= r->v[j])) v.push_back(l->v[i++]);
            else v.push_back(r->v[j++]);
        }

        //cout << s << " " << e << " : ";
        //for (auto x : v) cout << x << " "; cout << endl;
    }

    void update(int i, int ov, int nv) {
        //cout << "UPDATE " << i << " " << nv << endl;
        //cout << '\t'; for (auto y : v) cout << y << " "; cout << endl;
        if (s != e) {
            if (i <= m) l->update(i, ov, nv);
            else r->update(i, ov, nv);
        }
        stack<int> s;
        while (v.back() != ov) {
            s.push(v.back());
            v.pop_back();
            assert(!v.empty());
        }
        v.pop_back();

        while (!s.empty() && s.top() < nv) {
            v.push_back(s.top());
            s.pop();
        }
        v.push_back(nv);
        while (!s.empty()) {
            v.push_back(s.top());
            s.pop();
        }
    }

    void increase(int x) {
        if (s != e) {
            if (l->v.back() >= x) l->increase(x);
            if (r->v.back() >= x) r->increase(x);
        }

        //cout << "INCREASING " << s << " " << e << endl;
        for (int i = SZ(v)-1; i >= 0 && v[i] >= x; --i) {
            ++v[i];
        }
        //cout << '\t'; for (auto y : v) cout <<y << " " ; cout<< endl;
    }

    ll qmax(int x, int y) {
        //cout << "QMAX " << x << " " << y << " of " << s << " " << e << endl;
        if (s == x && e == y) { assert(!v.empty()); return v.back(); }
        else if (y <= m) return l->qmax(x, y);
        else if (x >  m) return r->qmax(x, y);
        else return max(l->qmax(x, m), r->qmax(m+1, y));
    }

    int qcntless(int x, int y, int z) {
        if (s == x && e == y) return lower_bound(ALL(v), z) - v.begin();
        else if (y <= m) return l->qcntless(x, y, z);
        else if (x >  m) return r->qcntless(x, y, z);
        else return l->qcntless(x, m, z) + r->qcntless(m+1, y, z);
    }

    void dbg() {
    }
} *root;

int main() {
    //freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, a; cin >> n >> a;
    int d[n+1];
    root = new node(1, n);
    set<int> delival;
    for (int i = 1; i <= n; ++i) {
        cin >> d[i];
        d[i] *= 500000;
        root->def(i, d[i]);
        delival.insert(d[i]);
    }
    root->build();

    int q; cin >> q;
    for (int qi = 0; qi < q; ++qi) {
        char t; cin >> t;
        if (t == 'F') {
            int b; cin >> b;
            //cout << "HI" << endl;

            if (b == a) cout << 0 << '\n';
            else if (b < a) {
                //cout << "CASE 1: " << endl;
                int maxi = root->qmax(b, a-1);
                //cout << maxi << endl;
                int cnt = root->qcntless(a+1, n, maxi);
                cout << cnt + (a-b) << '\n';
            }
            else {
                int maxi = root->qmax(a+1, b);
                //cout << "MAXI " << maxi << endl;
                int cnt = root->qcntless(1, a-1, maxi);
                cout << cnt + (b-a) << '\n';
            }
        }
        else {
            int i, e; cin >> i >> e;
            //cout << "OVAL " << d[i] << endl;
            //for (auto x : delival) cout << x << " "; cout << endl;

            ll ov = d[i];
            delival.erase(d[i]);

            auto it = delival.end();
            for (it = prev(it); e > 1; --e) {
                auto jt = prev(it);
                delival.insert(*it+1);
                delival.erase(it);
                it = jt;
            }
            //if (d[i] == *it) continue;

            d[i] = *it+1;
            delival.insert(d[i]);

            //cout << "NVAL " << d[i] << endl;
            //for (auto x : delival) cout << x << " "; cout << endl;
            root->increase(d[i]);
            root->update(i, ov, d[i]);
        }

        //cout << flush;
    }
}

Subtask #1
0 / 15.0

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

Subtask #2
0.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 16 ms 6272 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 17 ms 6784 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 21 ms 6784 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 740 ms 6976 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 39 ms 15480 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 33 ms 15608 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 51 ms 15608 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 753 ms 15608 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #3
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 382 ms 32020 KB Output isn't correct
2 Runtime error 192 ms 62580 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 216 ms 62632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 3 ms 384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Incorrect 851 ms 77116 KB Output isn't correct
6 Runtime error 628 ms 152684 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 518 ms 151780 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #4
0.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 8 ms 2304 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 13 ms 3584 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 200 ms 31348 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 122 ms 31220 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 8 ms 1636 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 847 ms 39152 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 35 ms 6784 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 245 ms 62420 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 735 ms 152564 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 7 ms 1664 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 55 ms 13176 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 1732 ms 126052 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 618 ms 151788 KB Execution killed with signal 11 (could be triggered by violating memory limits)