oj.uz

Submission #377441

# Submission time Handle Problem Language Result Execution time Memory
377441 2021-03-14T08:17:19 Z VEGAnn Specijacija (COCI20_specijacija) C++14
20 / 110
 4000 ms 133612 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]);

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

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

        /// 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 385 ms 133100 KB Output is correct
2 Correct 21 ms 10092 KB Output is correct
3 Correct 391 ms 133168 KB Output is correct
4 Correct 190 ms 69612 KB Output is correct
5 Correct 404 ms 133100 KB Output is correct
6 Correct 107 ms 39532 KB Output is correct
7 Correct 256 ms 133100 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 385 ms 133100 KB Output is correct
2 Correct 21 ms 10092 KB Output is correct
3 Correct 391 ms 133168 KB Output is correct
4 Correct 190 ms 69612 KB Output is correct
5 Correct 404 ms 133100 KB Output is correct
6 Correct 107 ms 39532 KB Output is correct
7 Correct 256 ms 133100 KB Output is correct
8 Correct 878 ms 1400 KB Output is correct
9 Correct 794 ms 1060 KB Output is correct
10 Correct 874 ms 1516 KB Output is correct
11 Correct 655 ms 1132 KB Output is correct
12 Correct 872 ms 1364 KB Output is correct
13 Correct 717 ms 1004 KB Output is correct
14 Correct 869 ms 1900 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 385 ms 133100 KB Output is correct
2 Correct 21 ms 10092 KB Output is correct
3 Correct 391 ms 133168 KB Output is correct
4 Correct 190 ms 69612 KB Output is correct
5 Correct 404 ms 133100 KB Output is correct
6 Correct 107 ms 39532 KB Output is correct
7 Correct 256 ms 133100 KB Output is correct
8 Correct 878 ms 1400 KB Output is correct
9 Correct 794 ms 1060 KB Output is correct
10 Correct 874 ms 1516 KB Output is correct
11 Correct 655 ms 1132 KB Output is correct
12 Correct 872 ms 1364 KB Output is correct
13 Correct 717 ms 1004 KB Output is correct
14 Correct 869 ms 1900 KB Output is correct
15 Execution timed out 4100 ms 133612 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 4110 ms 133484 KB Time limit exceeded
2 Halted 0 ms 0 KB -