oj.uz

Submission #378324

# Submission time Handle Problem Language Result Execution time Memory
378324 2021-03-16T13:38:54 Z kartel Specijacija (COCI20_specijacija) C++14
110 / 110
 1978 ms 62160 KB 
#include <bits/stdc++.h>
#define in(x) freopen(x, "r", stdin)
#define out(x) freopen(x, "w", stdout)
//#include <time.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
#define F first
#define S second
#define pb push_back
//#define M ll(1e9 + 7)
#define M ll(998244353)
#define sz(x) (int)x.size()
#define re return
#define oo ll(1e18)
#define el '\n'
#define pii pair <int, int>
#define all(x) (x).begin(), (x).end()
#define arr_all(x, n) (x + 1), (x + 1 + n)
#define vi vector<int>
#define eps (ld)1e-9
using namespace std;
typedef long long ll;
//using namespace __gnu_pbds;
//typedef tree <ll, null_type, less_equal <ll> , rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef double ld;
typedef unsigned long long ull;
typedef short int si;

const int N = 2e5 + 500;

int root[N], le[N * 40], ri[N * 40];

vector <int> t;

ll a[N];

ll last;
int n, q, tt;

int make(int &x) {
    int v = sz(t);

    t.pb(t[x]);
    le[v] = le[x];
    ri[v] = ri[x];

    return v;
}

void build(int v, int l, int r) {
    t[v] = r - l + 1;
    if (l == r) {
        return;
    }

    int md = (l + r) >> 1;
    t.pb(0); le[v] = sz(t) - 1;
    t.pb(0); ri[v] = sz(t) - 1;

    build(le[v], l, md);
    build(ri[v], md + 1, r);
}

void upd(int v, int l, int r, int ps) {
    if (l == r) {
        t[v] = 0;
        return;
    }
    else {
        t[v]--;
        int md = (l + r) >> 1;

        if (t[le[v]] < ps) {
            ri[v] = make(ri[v]);

            upd(ri[v], md + 1, r, ps - t[le[v]]);
        }
        else {
            le[v] = make(le[v]);

            upd(le[v], l, md, ps);
        }
    }
}

int sum(int v, int l, int r, int tl, int tr) {
    if (l == tl && r == tr) {
        return t[v];
    }

    if (l > r || tl > tr || l > tr || tl > r) {
        return 0;
    }

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

    return sum(le[v], l, md, tl, min(md, tr)) +
           sum(ri[v], md + 1, r, max(md + 1, tl), tr);
}

int getid(int v, int l, int r, int ps) {
    if (l == r) {
        return l;
    }
    else {
        int md = (l + r) >> 1;

        if (t[le[v]] < ps) {
            return getid(ri[v], md + 1, r, ps - t[le[v]]);
        }
        else {
            return getid(le[v], l, md, ps);
        }
    }
}

pair <ll, ll> get_id(ll x) {
    int l = 1;
    int r = n + 1;

    while (l < r) {
        int md = (l + r + 1) >> 1;

        if (md * 1ll * (md - 1) / 2ll < x) {
            l = md;
        }
        else {
            r = md - 1;
        }
    }

    return {l, x - (l * 1ll * (l - 1) / 2ll)};
}

int T[4 * N];

void update(int v, int l, int r, int ps, int val) {
    if (l == r) {
        T[v] = val;
    }
    else {
        int md = (l + r) >> 1;

        if (ps <= md) {
            update(v * 2, l, md, ps, val);
        }
        else {
            update(v * 2 + 1, md + 1, r, ps, val);
        }

        T[v] = min(T[v * 2], T[v * 2 + 1]);
    }
}

int get(int v, int l, int r, int tl, int tr) {
    if (l == tl && r == tr) {
        return T[v];
    }

    if (l > r || tl > tr || tl > r || l > tr) {
        return 1e9;
    }

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

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

int main()
{
//    mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());;
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//	in("1.in");
//	out("toys.out");
//    in("input.txt");
//    out("output.txt");
//    cerr.precision(9); cerr << fixed;
    cin >> n >> q >> tt;

    t.reserve(40 * n);

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    root[n + 1] = 0;
    t.pb(0);
    build(0, 1, n + 1);

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

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

        int nid = getid(root[i], 1, n + 1, id);
        update(1, 1, n + 1, nid, i);

        upd(root[i], 1, n + 1, id);
    }

    last = 0;
    ll MAXN = (n + 1) * 1ll * (n + 2) / 2ll;

    while (q--) {

        ll x, y;

        cin >> x >> y;

        x = (x - 1 + tt * last) % MAXN + 1;
        y = (y - 1 + tt * last) % MAXN + 1;

        pair <ll, ll> nx = get_id(x);
        pair <ll, ll> ny = get_id(y);

        int ft = getid(root[nx.F], 1, n + 1, nx.S),
            sd = getid(root[ny.F], 1, n + 1, ny.S);

        int lf = min(ft, sd) + 1;
        int rg = max(ft, sd);

        int l = min({get(1, 1, n + 1, lf, rg), (int)nx.F, (int)ny.F});

        ll ans = (l * 1ll * (l - 1) / 2ll);
        ans += sum(root[l], 1, n + 1, 1, ft);

        last = ans;
        cout << ans << el;
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 412 ms 53484 KB Output is correct
2 Correct 16 ms 4588 KB Output is correct
3 Correct 379 ms 53516 KB Output is correct
4 Correct 351 ms 28076 KB Output is correct
5 Correct 376 ms 53740 KB Output is correct
6 Correct 99 ms 16112 KB Output is correct
7 Correct 181 ms 53420 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 412 ms 53484 KB Output is correct
2 Correct 16 ms 4588 KB Output is correct
3 Correct 379 ms 53516 KB Output is correct
4 Correct 351 ms 28076 KB Output is correct
5 Correct 376 ms 53740 KB Output is correct
6 Correct 99 ms 16112 KB Output is correct
7 Correct 181 ms 53420 KB Output is correct
8 Correct 219 ms 1260 KB Output is correct
9 Correct 210 ms 1104 KB Output is correct
10 Correct 201 ms 1432 KB Output is correct
11 Correct 125 ms 1004 KB Output is correct
12 Correct 203 ms 1336 KB Output is correct
13 Correct 148 ms 1260 KB Output is correct
14 Correct 190 ms 1900 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 412 ms 53484 KB Output is correct
2 Correct 16 ms 4588 KB Output is correct
3 Correct 379 ms 53516 KB Output is correct
4 Correct 351 ms 28076 KB Output is correct
5 Correct 376 ms 53740 KB Output is correct
6 Correct 99 ms 16112 KB Output is correct
7 Correct 181 ms 53420 KB Output is correct
8 Correct 219 ms 1260 KB Output is correct
9 Correct 210 ms 1104 KB Output is correct
10 Correct 201 ms 1432 KB Output is correct
11 Correct 125 ms 1004 KB Output is correct
12 Correct 203 ms 1336 KB Output is correct
13 Correct 148 ms 1260 KB Output is correct
14 Correct 190 ms 1900 KB Output is correct
15 Correct 1688 ms 54296 KB Output is correct
16 Correct 913 ms 15340 KB Output is correct
17 Correct 1691 ms 60524 KB Output is correct
18 Correct 997 ms 15648 KB Output is correct
19 Correct 1687 ms 60524 KB Output is correct
20 Correct 840 ms 14316 KB Output is correct
21 Correct 1358 ms 61932 KB Output is correct

Subtask #4
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1978 ms 54456 KB Output is correct
2 Correct 1398 ms 30900 KB Output is correct
3 Correct 1755 ms 60524 KB Output is correct
4 Correct 1219 ms 30316 KB Output is correct
5 Correct 1662 ms 60712 KB Output is correct
6 Correct 1291 ms 33448 KB Output is correct
7 Correct 1366 ms 62160 KB Output is correct