oj.uz

Submission #378242

# Submission time Handle Problem Language Result Execution time Memory
378242 2021-03-16T10:20:40 Z kartel Specijacija (COCI20_specijacija) C++14
20 / 110
 4000 ms 54524 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];

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

    t.reserve(100 * 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;

        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 241 ms 51308 KB Output is correct
2 Correct 10 ms 4332 KB Output is correct
3 Correct 224 ms 53612 KB Output is correct
4 Correct 107 ms 28140 KB Output is correct
5 Correct 239 ms 53504 KB Output is correct
6 Correct 50 ms 16108 KB Output is correct
7 Correct 116 ms 53484 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 51308 KB Output is correct
2 Correct 10 ms 4332 KB Output is correct
3 Correct 224 ms 53612 KB Output is correct
4 Correct 107 ms 28140 KB Output is correct
5 Correct 239 ms 53504 KB Output is correct
6 Correct 50 ms 16108 KB Output is correct
7 Correct 116 ms 53484 KB Output is correct
8 Correct 437 ms 3544 KB Output is correct
9 Correct 344 ms 3436 KB Output is correct
10 Correct 424 ms 3436 KB Output is correct
11 Correct 214 ms 2796 KB Output is correct
12 Correct 420 ms 3308 KB Output is correct
13 Correct 271 ms 3116 KB Output is correct
14 Correct 454 ms 4076 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 51308 KB Output is correct
2 Correct 10 ms 4332 KB Output is correct
3 Correct 224 ms 53612 KB Output is correct
4 Correct 107 ms 28140 KB Output is correct
5 Correct 239 ms 53504 KB Output is correct
6 Correct 50 ms 16108 KB Output is correct
7 Correct 116 ms 53484 KB Output is correct
8 Correct 437 ms 3544 KB Output is correct
9 Correct 344 ms 3436 KB Output is correct
10 Correct 424 ms 3436 KB Output is correct
11 Correct 214 ms 2796 KB Output is correct
12 Correct 420 ms 3308 KB Output is correct
13 Correct 271 ms 3116 KB Output is correct
14 Correct 454 ms 4076 KB Output is correct
15 Execution timed out 4078 ms 54524 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 4091 ms 51864 KB Time limit exceeded
2 Halted 0 ms 0 KB -