oj.uz

Submission #377442

# Submission time Handle Problem Language Result Execution time Memory
377442 2021-03-14T08:18:47 Z VEGAnn Specijacija (COCI20_specijacija) C++14
20 / 110
 4000 ms 133572 KB 
#include <bits/stdc++.h>
#define i2 array<ll,2>
using namespace std;
typedef long long ll;
const ll oo = 2e9;
const ll N = 200100;
const ll M = 10;
const ll PW = 10;
const ll HPW = 233;
const ll md = ll(1e9) + 7;
ll n, a[N], t;
ll q;

struct seg_tree{
    seg_tree *l, *r;
    ll sm;

    seg_tree(): l(0), r(0), sm(0) {}

    seg_tree(seg_tree *v): l(v -> l), r(v -> r), sm(v -> sm) {}

    void build(ll tl, ll tr){
        sm = tr - tl + 1;

        if (tl == tr) return;

        ll md = (tl + tr) >> 1;

        l = new seg_tree();
        r = new seg_tree();

        l -> build(tl, md);
        r -> build(md + 1, tr);
    }

    void delt(ll tl, ll tr, ll ind){
        sm--;

        if (tl == tr) return;

        ll md = (tl + tr) >> 1;

        if (l -> sm < ind){
            r = new seg_tree(r);

            r -> delt(md + 1, tr, ind - (l -> sm));
        } else {
            l = new seg_tree(l);

            l -> delt(tl, md, ind);
        }
    }

    ll get(ll tl, ll tr, ll ql, ll qr){
        if (ql > qr) return 0;

        if (tl == ql && tr == qr) return sm;

        ll md = (tl + tr) >> 1;

        return (l -> get(tl, md, ql, min(qr, md))) +
                (r -> get(md + 1, tr, max(md + 1, ql), qr));
    }

    ll get_by_cnt(ll tl, ll tr, ll ind){
        if (tl == tr) return tl;

        ll md = (tl + tr) >> 1;

        if (l -> sm < ind){
            return r -> get_by_cnt(md + 1, tr, ind - (l -> sm));
        } else {
            return l -> get_by_cnt(tl, md, ind);
        }
    }
};

seg_tree *root[N];

/// 0 -- layer, 1 -- index

i2 get_id(ll x){
    ll l = 1, r = n + 1;

    while (l < r){
        ll md = (l + r + 1) >> 1;

        if (x > md * (md - 1) / 2)
            l = md;
        else r = md - 1;
    }

    return {l, x - (l * (l - 1) / 2)};
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

#ifdef _LOCAL
    freopen("in.txt","r",stdin);
#endif // _LOCAL

    cin >> n >> q >> t;

    for (ll i = 1; i <= n; i++)
        cin >> a[i];

    root[n + 1] = new seg_tree();

    root[n + 1] -> build(1, n + 1);

    for (ll i = n; i > 0; i--){
        root[i] = new seg_tree(root[i + 1]);

        ll id = a[i] - (ll(i) * (ll(i) - 1ll) / 2ll);

        root[i] -> delt(1, n + 1, id + 1);
    }

    ll last = 0;
    ll BIG = (ll(n) + 1) * (ll(n) + 2) / 2ll;

    for (; q; q--){
        ll x, y; cin >> x >> y;

        x = ((x - 1) + t * last) % BIG + 1;
        y = ((y - 1) + t * last) % BIG + 1;

        i2 nw_x = get_id(x);
        i2 nw_y = get_id(y);

        /// do binary search

        ll lf = 1, rt = min(nw_x[0], nw_y[0]);

        ll ps1 = root[nw_x[0]] -> get_by_cnt(1, n + 1, nw_x[1]);
        ll ps2 = root[nw_y[0]] -> get_by_cnt(1, n + 1, nw_y[1]);

        ll MN = min(ps1, ps2);
        ll MX = max(ps1, ps2);

        while (lf < rt){
            ll md = (lf + rt + 1) >> 1;

            if (root[md] -> get(1, n + 1, MN + 1, MX) == 0)
                lf = md;
            else rt = md - 1;
        }

        /// lf -- new layer
        /// get new id

        ll res = ll(lf) * (ll(lf) - 1ll) / 2ll;

        res += root[lf] -> get(1, n + 1, 1, ps1);

        last = res;

//        cout << res << '\n';
        cout << res << endl;
    }

    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 379 ms 132972 KB Output is correct
2 Correct 21 ms 10092 KB Output is correct
3 Correct 383 ms 133228 KB Output is correct
4 Correct 209 ms 69612 KB Output is correct
5 Correct 380 ms 133228 KB Output is correct
6 Correct 106 ms 39640 KB Output is correct
7 Correct 255 ms 133100 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 379 ms 132972 KB Output is correct
2 Correct 21 ms 10092 KB Output is correct
3 Correct 383 ms 133228 KB Output is correct
4 Correct 209 ms 69612 KB Output is correct
5 Correct 380 ms 133228 KB Output is correct
6 Correct 106 ms 39640 KB Output is correct
7 Correct 255 ms 133100 KB Output is correct
8 Correct 890 ms 1516 KB Output is correct
9 Correct 806 ms 1132 KB Output is correct
10 Correct 881 ms 1504 KB Output is correct
11 Correct 688 ms 876 KB Output is correct
12 Correct 888 ms 1264 KB Output is correct
13 Correct 732 ms 1132 KB Output is correct
14 Correct 884 ms 1900 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 379 ms 132972 KB Output is correct
2 Correct 21 ms 10092 KB Output is correct
3 Correct 383 ms 133228 KB Output is correct
4 Correct 209 ms 69612 KB Output is correct
5 Correct 380 ms 133228 KB Output is correct
6 Correct 106 ms 39640 KB Output is correct
7 Correct 255 ms 133100 KB Output is correct
8 Correct 890 ms 1516 KB Output is correct
9 Correct 806 ms 1132 KB Output is correct
10 Correct 881 ms 1504 KB Output is correct
11 Correct 688 ms 876 KB Output is correct
12 Correct 888 ms 1264 KB Output is correct
13 Correct 732 ms 1132 KB Output is correct
14 Correct 884 ms 1900 KB Output is correct
15 Execution timed out 4075 ms 133572 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4072 ms 133448 KB Time limit exceeded
2 Halted 0 ms 0 KB -