oj.uz

Submission #378191

# Submission time Handle Problem Language Result Execution time Memory
378191 2021-03-16T07:13:20 Z kartel Specijacija (COCI20_specijacija) C++14
20 / 110
 4000 ms 52064 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 * 100], ri[N * 100];

int t[N * 100];

ll a[N];
int plast = 0;

ll last;
int n, q, tt;

int make(int x) {
    int v = plast++;

    t[v] = 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[plast++] = 0; le[v] = plast - 1;
    t[plast++] = 0; ri[v] = plast - 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 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;

//    clock_t tStart = clock();

    cin >> n >> q >> tt;

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

    root[n + 1] = 0;
    t[plast++] = 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;

        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 l = 1, r = min(nx.F, ny.F);

        int L = min(ft, sd) + 1;
        int R = max(ft, sd);

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

            if (sum(root[md], 1, n + 1, L, R) == 0) {
                l = md;
            }
            else {
                r = md - 1;
            }
        }

        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 246 ms 51308 KB Output is correct
2 Correct 9 ms 4076 KB Output is correct
3 Correct 213 ms 51436 KB Output is correct
4 Correct 94 ms 26988 KB Output is correct
5 Correct 213 ms 51308 KB Output is correct
6 Correct 50 ms 15468 KB Output is correct
7 Correct 97 ms 51308 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 246 ms 51308 KB Output is correct
2 Correct 9 ms 4076 KB Output is correct
3 Correct 213 ms 51436 KB Output is correct
4 Correct 94 ms 26988 KB Output is correct
5 Correct 213 ms 51308 KB Output is correct
6 Correct 50 ms 15468 KB Output is correct
7 Correct 97 ms 51308 KB Output is correct
8 Correct 433 ms 1168 KB Output is correct
9 Correct 356 ms 916 KB Output is correct
10 Correct 439 ms 1132 KB Output is correct
11 Correct 266 ms 876 KB Output is correct
12 Correct 436 ms 1004 KB Output is correct
13 Correct 288 ms 908 KB Output is correct
14 Correct 438 ms 1772 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 246 ms 51308 KB Output is correct
2 Correct 9 ms 4076 KB Output is correct
3 Correct 213 ms 51436 KB Output is correct
4 Correct 94 ms 26988 KB Output is correct
5 Correct 213 ms 51308 KB Output is correct
6 Correct 50 ms 15468 KB Output is correct
7 Correct 97 ms 51308 KB Output is correct
8 Correct 433 ms 1168 KB Output is correct
9 Correct 356 ms 916 KB Output is correct
10 Correct 439 ms 1132 KB Output is correct
11 Correct 266 ms 876 KB Output is correct
12 Correct 436 ms 1004 KB Output is correct
13 Correct 288 ms 908 KB Output is correct
14 Correct 438 ms 1772 KB Output is correct
15 Execution timed out 4050 ms 52064 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 4062 ms 51812 KB Time limit exceeded
2 Halted 0 ms 0 KB -