oj.uz

Submission #101595

# Submission time Handle Problem Language Result Execution time Memory
101595 2019-03-19T04:50:39 Z lyc Cake (CEOI14_cake) C++14
0 / 100
 787 ms 66044 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];
        root->def(i, 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;
            if (b == a) cout << 0 << '\n';
            else if (b < a) {
                int maxi = root->qmax(b, a-1);
                int cnt = root->qcntless(a+1, n, maxi);
                cout << cnt + (a-b) << '\n';
            }
            else {
                int maxi = root->qmax(a+1, b);
                int cnt = root->qcntless(1, a-1, maxi);
                cout << cnt + (b-a) << '\n';
            }
        }
        else {
            int i, e; cin >> i >> e;
        }
    }
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 84 ms 2832 KB Output isn't correct
2 Incorrect 115 ms 3064 KB Output isn't correct
3 Incorrect 102 ms 2944 KB Output isn't correct
4 Incorrect 91 ms 3016 KB Output isn't correct
5 Incorrect 112 ms 6656 KB Output isn't correct
6 Incorrect 135 ms 6784 KB Output isn't correct
7 Incorrect 134 ms 6820 KB Output isn't correct
8 Incorrect 119 ms 6796 KB Output isn't correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 234 ms 27148 KB Output isn't correct
2 Incorrect 208 ms 27248 KB Output isn't correct
3 Incorrect 146 ms 26992 KB Output isn't correct
4 Incorrect 2 ms 384 KB Output isn't correct
5 Incorrect 427 ms 64884 KB Output isn't correct
6 Incorrect 357 ms 64804 KB Output isn't correct
7 Incorrect 240 ms 64852 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 1260 KB Output isn't correct
2 Incorrect 32 ms 1744 KB Output isn't correct
3 Incorrect 133 ms 13620 KB Output isn't correct
4 Incorrect 124 ms 13428 KB Output isn't correct
5 Incorrect 82 ms 1144 KB Output isn't correct
6 Incorrect 203 ms 17056 KB Output isn't correct
7 Incorrect 108 ms 3448 KB Output isn't correct
8 Incorrect 121 ms 26508 KB Output isn't correct
9 Incorrect 787 ms 66016 KB Output isn't correct
10 Incorrect 173 ms 2208 KB Output isn't correct
11 Incorrect 288 ms 7160 KB Output isn't correct
12 Incorrect 745 ms 55188 KB Output isn't correct
13 Incorrect 534 ms 66044 KB Output isn't correct