oj.uz

Submission #377439

# Submission time Handle Problem Language Result Execution time Memory
377439 2021-03-14T08:14:31 Z VEGAnn Specijacija (COCI20_specijacija) C++14
20 / 110
 4000 ms 139768 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];
int q, t;

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

    ll 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 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);

        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 lf = 1, rt = min(nw_x[0], nw_y[0]);

        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]);

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

            if (root[md] -> get(1, n + 1, 1, ps1) ==
                root[md] -> get(1, n + 1, 1, ps2))
                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;
}

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 407 ms 135376 KB Output is correct
2 Correct 24 ms 10220 KB Output is correct
3 Correct 401 ms 135204 KB Output is correct
4 Correct 196 ms 70764 KB Output is correct
5 Correct 409 ms 135148 KB Output is correct
6 Correct 108 ms 40172 KB Output is correct
7 Correct 275 ms 135204 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 407 ms 135376 KB Output is correct
2 Correct 24 ms 10220 KB Output is correct
3 Correct 401 ms 135204 KB Output is correct
4 Correct 196 ms 70764 KB Output is correct
5 Correct 409 ms 135148 KB Output is correct
6 Correct 108 ms 40172 KB Output is correct
7 Correct 275 ms 135204 KB Output is correct
8 Correct 905 ms 3964 KB Output is correct
9 Correct 821 ms 3484 KB Output is correct
10 Correct 909 ms 3996 KB Output is correct
11 Correct 730 ms 2840 KB Output is correct
12 Correct 899 ms 4212 KB Output is correct
13 Correct 740 ms 3180 KB Output is correct
14 Correct 902 ms 4668 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 407 ms 135376 KB Output is correct
2 Correct 24 ms 10220 KB Output is correct
3 Correct 401 ms 135204 KB Output is correct
4 Correct 196 ms 70764 KB Output is correct
5 Correct 409 ms 135148 KB Output is correct
6 Correct 108 ms 40172 KB Output is correct
7 Correct 275 ms 135204 KB Output is correct
8 Correct 905 ms 3964 KB Output is correct
9 Correct 821 ms 3484 KB Output is correct
10 Correct 909 ms 3996 KB Output is correct
11 Correct 730 ms 2840 KB Output is correct
12 Correct 899 ms 4212 KB Output is correct
13 Correct 740 ms 3180 KB Output is correct
14 Correct 902 ms 4668 KB Output is correct
15 Execution timed out 4077 ms 139740 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 4070 ms 139768 KB Time limit exceeded
2 Halted 0 ms 0 KB -