Submission #377448

#	Time	Username	Problem	Language	Result	Execution time	Memory
377448		VEGAnn	Specijacija (COCI20_specijacija)	C++14	110 / 110	2110 ms	143996 KiB

Main

#include <bits/stdc++.h>
#define i2 array<int,2>
using namespace std;
typedef long long ll;
const int oo = 2e9;
const int N = 200100;
const int M = 10;
const int PW = 10;
const int HPW = 233;
const int md = int(1e9) + 7;
ll n, a[N], t;
int q;

struct seg_tree{
    seg_tree *l, *r;
    int 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(int tl, int tr){
        sm = tr - tl + 1;

        if (tl == tr) return;

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

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

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

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

        if (tl == tr) return;

        int 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);
        }
    }

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

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

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

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

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

        int 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 st[4 * N];

void update(int v, int l, int r, int ps, int vl){
    if (l == r){
        st[v] = vl;
        return;
    }

    int md = (l + r) >> 1;

    if (ps <= md)
        update(v + v, l, md, ps, vl);
    else update(v + v + 1, md + 1, r, ps, vl);

    st[v] = min(st[v + v], st[v + v + 1]);
}

int get_min(int v, int tl, int tr, int l, int r){
    if (l > r) return oo;

    if (tl == l && tr == r) return st[v];

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

    return min(get_min(v + v, tl, md, l, min(r, md)),
               get_min(v + v + 1, md + 1, tr, max(md + 1, l), r));
}

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 (int i = 1; i <= n; i++)
        cin >> a[i];

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

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

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

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

        int loc = root[i] -> get_by_cnt(1, n + 1, id + 1);

        update(1, 1, n + 1, loc, i);

        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


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

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

//        int lf = 1, rt = min(nw_x[0], nw_y[0]);
//        while (lf < rt){
//            int md = (lf + rt + 1) >> 1;
//
//            if (root[md] -> get(1, n + 1, MN + 1, MX) == 0)
//                lf = md;
//            else rt = md - 1;
//        }

        int lf = min(min(nw_x[0], nw_y[0]), get_min(1, 1, n + 1, MN + 1, MX));

        /// 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;
}

Compilation message (stderr)

Main.cpp: In function 'std::array<int, 2> get_id(ll)':
Main.cpp:93:13: warning: narrowing conversion of 'l' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
   93 |     return {l, x - (l * (l - 1) / 2)};
      |             ^
Main.cpp:93:18: warning: narrowing conversion of '(x - ((l * (l - 1)) / 2))' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
   93 |     return {l, x - (l * (l - 1) / 2)};
      |                ~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 30 / 30
• Subtask 4: 60 / 60