oj.uz

Submission #378243

# Submission time Handle Problem Language Result Execution time Memory
378243 2021-03-16T10:24:08 Z kartel Specijacija (COCI20_specijacija) C++14
20 / 110
 4000 ms 52008 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 232 ms 51308 KB Output is correct
2 Correct 11 ms 4076 KB Output is correct
3 Correct 225 ms 51308 KB Output is correct
4 Correct 109 ms 27084 KB Output is correct
5 Correct 226 ms 51308 KB Output is correct
6 Correct 52 ms 15468 KB Output is correct
7 Correct 113 ms 51308 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 232 ms 51308 KB Output is correct
2 Correct 11 ms 4076 KB Output is correct
3 Correct 225 ms 51308 KB Output is correct
4 Correct 109 ms 27084 KB Output is correct
5 Correct 226 ms 51308 KB Output is correct
6 Correct 52 ms 15468 KB Output is correct
7 Correct 113 ms 51308 KB Output is correct
8 Correct 437 ms 1132 KB Output is correct
9 Correct 352 ms 1004 KB Output is correct
10 Correct 441 ms 1288 KB Output is correct
11 Correct 217 ms 1004 KB Output is correct
12 Correct 456 ms 1260 KB Output is correct
13 Correct 277 ms 1004 KB Output is correct
14 Correct 441 ms 1772 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 232 ms 51308 KB Output is correct
2 Correct 11 ms 4076 KB Output is correct
3 Correct 225 ms 51308 KB Output is correct
4 Correct 109 ms 27084 KB Output is correct
5 Correct 226 ms 51308 KB Output is correct
6 Correct 52 ms 15468 KB Output is correct
7 Correct 113 ms 51308 KB Output is correct
8 Correct 437 ms 1132 KB Output is correct
9 Correct 352 ms 1004 KB Output is correct
10 Correct 441 ms 1288 KB Output is correct
11 Correct 217 ms 1004 KB Output is correct
12 Correct 456 ms 1260 KB Output is correct
13 Correct 277 ms 1004 KB Output is correct
14 Correct 441 ms 1772 KB Output is correct
15 Execution timed out 4098 ms 51812 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 4064 ms 52008 KB Time limit exceeded
2 Halted 0 ms 0 KB -