oj.uz

Submission #101621

# Submission time Handle Problem Language Result Execution time Memory
101621 2019-03-19T05:22:10 Z lyc Cake (CEOI14_cake) C++14
83.3333 / 100
 2000 ms 38168 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, v;
    node *l, *r;
    node(int _s, int _e): s(_s), e(_e), m((_s+_e)/2), v(0) {
        if (s != e) {
            l = new node(s, m);
            r = new node(m+1, e);
        }
    }

    void update(int i, int x) {
        if (s == e) { v = x; return; }
        else if (i<=m)l->update(i, x);
        else r->update(i, x);
        v = max(l->v, r->v);
    }

    int qmax(int x, int y) {
        if (x > y) return 0;
        if (s == x && e == y) return v;
        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));
    }
} *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<ii> s;
    for (int i = 1; i <= n; ++i) {
        cin >> d[i];
        root->update(i, d[i]);
        s.insert(ii(d[i], i));
    }

    int q; cin >> q;
    for (int qi = 0; qi < q; ++qi) {
        char t; cin >> t;
        if (t == 'F') {
            int b; cin >> b;
            if (b == a) cout << 0 << '\n';
            else if (b < a) {
                int maxi = root->qmax(b, a-1);
                //int idx = root->qrightidx(a+1, n, maxi);
                int lo = a+1, hi = n+1;
                while (lo < hi) {
                    int mid = (lo+hi)/2;
                    if (root->qmax(a+1, mid) < maxi) lo = mid+1;
                    else hi = mid;
                }
                int idx = hi;

                //cout << "HI " << idx << endl;
                cout << idx-1-b << '\n';
            }
            else {
                int maxi = root->qmax(a+1, b);
                //int idx = root->qleftidx(1, a-1, maxi);
                int lo = 1, hi = a;
                while (lo < hi) {
                    int mid = (lo+hi)/2;
                    if (root->qmax(mid, a-1) < maxi) hi = mid;
                    else lo = mid+1;
                }
                int idx = lo-1;

                //cout << "NO " << idx << endl;
                //cout << "\t" << root->qmax(idx, a-1) << endl;
                cout << b-idx-1 << '\n';
            }
        }
        else {
            int j, e; cin >> j >> e;

            s.erase(ii(d[j], j));
            vector<int> modified;
            for (int i = 0; i < e-1; ++i) {
                int idx = s.rbegin()->sc;
                s.erase(prev(s.end()));
                root->update(idx, d[idx]+1);
                ++d[idx];
                modified.push_back(idx);
            }
            root->update(j, s.rbegin()->fi+1);
            d[j] = s.rbegin()->fi+1;
            modified.push_back(j);

            for (auto x : modified) {
                s.insert(ii(d[x], x));
            }
        }
        //cout << flush;
    }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 13 ms 512 KB Output is correct
5 Correct 30 ms 1792 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 740 ms 1756 KB Output is correct
2 Correct 347 ms 1792 KB Output is correct
3 Correct 537 ms 1792 KB Output is correct
4 Correct 266 ms 1912 KB Output is correct
5 Correct 889 ms 3960 KB Output is correct
6 Correct 723 ms 3996 KB Output is correct
7 Correct 594 ms 4000 KB Output is correct
8 Correct 289 ms 3996 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 416 ms 15452 KB Output is correct
2 Correct 246 ms 15320 KB Output is correct
3 Correct 280 ms 15196 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 754 ms 37192 KB Output is correct
6 Correct 731 ms 37228 KB Output is correct
7 Correct 396 ms 36964 KB Output is correct

Subtask #4
33.333333 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 860 KB Output is correct
2 Correct 75 ms 1208 KB Output is correct
3 Correct 329 ms 7876 KB Output is correct
4 Correct 316 ms 7824 KB Output is correct
5 Correct 192 ms 1036 KB Output is correct
6 Correct 586 ms 10324 KB Output is correct
7 Correct 390 ms 2296 KB Output is correct
8 Correct 520 ms 14968 KB Output is correct
9 Execution timed out 2037 ms 37816 KB Time limit exceeded
10 Correct 726 ms 1824 KB Output is correct
11 Correct 1373 ms 4640 KB Output is correct
12 Execution timed out 2037 ms 30568 KB Time limit exceeded
13 Execution timed out 2021 ms 38168 KB Time limit exceeded