oj.uz

Submission #377448

# Submission time Handle Problem Language Result Execution time Memory
377448 2021-03-14T08:29:12 Z VEGAnn Specijacija (COCI20_specijacija) C++14
110 / 110
 2110 ms 143996 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 464 ms 135144 KB Output is correct
2 Correct 26 ms 10348 KB Output is correct
3 Correct 482 ms 135148 KB Output is correct
4 Correct 233 ms 70764 KB Output is correct
5 Correct 478 ms 135148 KB Output is correct
6 Correct 128 ms 40044 KB Output is correct
7 Correct 319 ms 135148 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 464 ms 135144 KB Output is correct
2 Correct 26 ms 10348 KB Output is correct
3 Correct 482 ms 135148 KB Output is correct
4 Correct 233 ms 70764 KB Output is correct
5 Correct 478 ms 135148 KB Output is correct
6 Correct 128 ms 40044 KB Output is correct
7 Correct 319 ms 135148 KB Output is correct
8 Correct 648 ms 1516 KB Output is correct
9 Correct 617 ms 1068 KB Output is correct
10 Correct 664 ms 1296 KB Output is correct
11 Correct 568 ms 872 KB Output is correct
12 Correct 687 ms 1388 KB Output is correct
13 Correct 579 ms 1004 KB Output is correct
14 Correct 641 ms 1900 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 464 ms 135144 KB Output is correct
2 Correct 26 ms 10348 KB Output is correct
3 Correct 482 ms 135148 KB Output is correct
4 Correct 233 ms 70764 KB Output is correct
5 Correct 478 ms 135148 KB Output is correct
6 Correct 128 ms 40044 KB Output is correct
7 Correct 319 ms 135148 KB Output is correct
8 Correct 648 ms 1516 KB Output is correct
9 Correct 617 ms 1068 KB Output is correct
10 Correct 664 ms 1296 KB Output is correct
11 Correct 568 ms 872 KB Output is correct
12 Correct 687 ms 1388 KB Output is correct
13 Correct 579 ms 1004 KB Output is correct
14 Correct 641 ms 1900 KB Output is correct
15 Correct 2016 ms 136180 KB Output is correct
16 Correct 1356 ms 30972 KB Output is correct
17 Correct 2045 ms 142588 KB Output is correct
18 Correct 1387 ms 31724 KB Output is correct
19 Correct 2062 ms 142188 KB Output is correct
20 Correct 1359 ms 28524 KB Output is correct
21 Correct 1888 ms 143996 KB Output is correct

Subtask #4
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 2065 ms 136296 KB Output is correct
2 Correct 1681 ms 69160 KB Output is correct
3 Correct 2082 ms 142444 KB Output is correct
4 Correct 1669 ms 67180 KB Output is correct
5 Correct 2110 ms 142488 KB Output is correct
6 Correct 1663 ms 74988 KB Output is correct
7 Correct 1890 ms 143720 KB Output is correct