oj.uz

Submission #378247

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

        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 233 ms 51308 KB Output is correct
2 Correct 10 ms 4076 KB Output is correct
3 Correct 242 ms 51340 KB Output is correct
4 Correct 115 ms 27116 KB Output is correct
5 Correct 243 ms 51308 KB Output is correct
6 Correct 53 ms 15468 KB Output is correct
7 Correct 114 ms 51308 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 233 ms 51308 KB Output is correct
2 Correct 10 ms 4076 KB Output is correct
3 Correct 242 ms 51340 KB Output is correct
4 Correct 115 ms 27116 KB Output is correct
5 Correct 243 ms 51308 KB Output is correct
6 Correct 53 ms 15468 KB Output is correct
7 Correct 114 ms 51308 KB Output is correct
8 Correct 433 ms 1080 KB Output is correct
9 Correct 349 ms 1132 KB Output is correct
10 Correct 438 ms 1208 KB Output is correct
11 Correct 216 ms 876 KB Output is correct
12 Correct 432 ms 1004 KB Output is correct
13 Correct 278 ms 1004 KB Output is correct
14 Correct 450 ms 1772 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 233 ms 51308 KB Output is correct
2 Correct 10 ms 4076 KB Output is correct
3 Correct 242 ms 51340 KB Output is correct
4 Correct 115 ms 27116 KB Output is correct
5 Correct 243 ms 51308 KB Output is correct
6 Correct 53 ms 15468 KB Output is correct
7 Correct 114 ms 51308 KB Output is correct
8 Correct 433 ms 1080 KB Output is correct
9 Correct 349 ms 1132 KB Output is correct
10 Correct 438 ms 1208 KB Output is correct
11 Correct 216 ms 876 KB Output is correct
12 Correct 432 ms 1004 KB Output is correct
13 Correct 278 ms 1004 KB Output is correct
14 Correct 450 ms 1772 KB Output is correct
15 Execution timed out 4051 ms 52076 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 4098 ms 51872 KB Time limit exceeded
2 Halted 0 ms 0 KB -