Submission #377442

#	Time	Username	Problem	Language	Result	Execution time	Memory
377442		VEGAnn	Specijacija (COCI20_specijacija)	C++14	20 / 110	4075 ms	133572 KiB

Main

#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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 0 / 30
• Subtask 4: 0 / 60