oj.uz

Submission #377444

# Submission time Handle Problem Language Result Execution time Memory
377444 2021-03-14T08:22:14 Z VEGAnn Specijacija (COCI20_specijacija) C++14
20 / 110
 4000 ms 133564 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 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 390 ms 133008 KB Output is correct
2 Correct 24 ms 10092 KB Output is correct
3 Correct 395 ms 133152 KB Output is correct
4 Correct 187 ms 69740 KB Output is correct
5 Correct 406 ms 133100 KB Output is correct
6 Correct 102 ms 39532 KB Output is correct
7 Correct 285 ms 132972 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 390 ms 133008 KB Output is correct
2 Correct 24 ms 10092 KB Output is correct
3 Correct 395 ms 133152 KB Output is correct
4 Correct 187 ms 69740 KB Output is correct
5 Correct 406 ms 133100 KB Output is correct
6 Correct 102 ms 39532 KB Output is correct
7 Correct 285 ms 132972 KB Output is correct
8 Correct 876 ms 1412 KB Output is correct
9 Correct 807 ms 1132 KB Output is correct
10 Correct 875 ms 1516 KB Output is correct
11 Correct 674 ms 876 KB Output is correct
12 Correct 878 ms 1388 KB Output is correct
13 Correct 750 ms 1132 KB Output is correct
14 Correct 877 ms 1900 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 390 ms 133008 KB Output is correct
2 Correct 24 ms 10092 KB Output is correct
3 Correct 395 ms 133152 KB Output is correct
4 Correct 187 ms 69740 KB Output is correct
5 Correct 406 ms 133100 KB Output is correct
6 Correct 102 ms 39532 KB Output is correct
7 Correct 285 ms 132972 KB Output is correct
8 Correct 876 ms 1412 KB Output is correct
9 Correct 807 ms 1132 KB Output is correct
10 Correct 875 ms 1516 KB Output is correct
11 Correct 674 ms 876 KB Output is correct
12 Correct 878 ms 1388 KB Output is correct
13 Correct 750 ms 1132 KB Output is correct
14 Correct 877 ms 1900 KB Output is correct
15 Execution timed out 4104 ms 133464 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 4106 ms 133564 KB Time limit exceeded
2 Halted 0 ms 0 KB -