oj.uz

Submission #101615

# Submission time Handle Problem Language Result Execution time Memory
101615 2019-03-19T05:19:00 Z lyc Cake (CEOI14_cake) C++14
0 / 100
 2000 ms 36864 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);
    for (int i = 1; i <= n; ++i) {
        cin >> d[i];
        root->update(i, d[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;

            set<ii> s;
            for (int i = 1; i <= n; ++i) if (i != j) {
                s.insert(ii(d[i], i));
            }

            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];
            }
            root->update(j, s.rbegin()->fi+1);
            d[j] = s.rbegin()->fi+1;
        }
        //cout << flush;
    }
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 286 ms 512 KB Output is correct
5 Execution timed out 2051 ms 1912 KB Time limit exceeded

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2059 ms 1664 KB Time limit exceeded
2 Execution timed out 2072 ms 1792 KB Time limit exceeded
3 Execution timed out 2021 ms 1792 KB Time limit exceeded
4 Execution timed out 2041 ms 1792 KB Time limit exceeded
5 Execution timed out 2058 ms 3968 KB Time limit exceeded
6 Execution timed out 2056 ms 3968 KB Time limit exceeded
7 Execution timed out 2021 ms 3968 KB Time limit exceeded
8 Execution timed out 2096 ms 3968 KB Time limit exceeded

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2056 ms 15220 KB Time limit exceeded
2 Execution timed out 2035 ms 15352 KB Time limit exceeded
3 Execution timed out 2045 ms 15256 KB Time limit exceeded
4 Correct 2 ms 384 KB Output is correct
5 Execution timed out 2047 ms 36612 KB Time limit exceeded
6 Execution timed out 2045 ms 36864 KB Time limit exceeded
7 Execution timed out 2045 ms 36828 KB Time limit exceeded

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2024 ms 944 KB Time limit exceeded
2 Execution timed out 2048 ms 1144 KB Time limit exceeded
3 Execution timed out 2047 ms 7672 KB Time limit exceeded
4 Execution timed out 2050 ms 7672 KB Time limit exceeded
5 Execution timed out 2029 ms 760 KB Time limit exceeded
6 Execution timed out 2074 ms 9844 KB Time limit exceeded
7 Execution timed out 2045 ms 1792 KB Time limit exceeded
8 Execution timed out 2054 ms 14840 KB Time limit exceeded
9 Execution timed out 2016 ms 36472 KB Time limit exceeded
10 Execution timed out 2025 ms 796 KB Time limit exceeded
11 Execution timed out 2097 ms 3148 KB Time limit exceeded
12 Execution timed out 2066 ms 29316 KB Time limit exceeded
13 Execution timed out 2102 ms 36676 KB Time limit exceeded