oj.uz

답안 #378188

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
378188 2021-03-16T07:10:10 Z kartel Specijacija (COCI20_specijacija) C++14
20 / 110
 4000 ms 58404 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;

    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

# 결과 실행 시간 메모리 Grader output
1 Correct 243 ms 51404 KB Output is correct
2 Correct 11 ms 4968 KB Output is correct
3 Correct 252 ms 53564 KB Output is correct
4 Correct 119 ms 35664 KB Output is correct
5 Correct 237 ms 53500 KB Output is correct
6 Correct 58 ms 18268 KB Output is correct
7 Correct 125 ms 53564 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 243 ms 51404 KB Output is correct
2 Correct 11 ms 4968 KB Output is correct
3 Correct 252 ms 53564 KB Output is correct
4 Correct 119 ms 35664 KB Output is correct
5 Correct 237 ms 53500 KB Output is correct
6 Correct 58 ms 18268 KB Output is correct
7 Correct 125 ms 53564 KB Output is correct
8 Correct 424 ms 3820 KB Output is correct
9 Correct 345 ms 3308 KB Output is correct
10 Correct 432 ms 4004 KB Output is correct
11 Correct 210 ms 2796 KB Output is correct
12 Correct 424 ms 4092 KB Output is correct
13 Correct 267 ms 3180 KB Output is correct
14 Correct 439 ms 4460 KB Output is correct

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 243 ms 51404 KB Output is correct
2 Correct 11 ms 4968 KB Output is correct
3 Correct 252 ms 53564 KB Output is correct
4 Correct 119 ms 35664 KB Output is correct
5 Correct 237 ms 53500 KB Output is correct
6 Correct 58 ms 18268 KB Output is correct
7 Correct 125 ms 53564 KB Output is correct
8 Correct 424 ms 3820 KB Output is correct
9 Correct 345 ms 3308 KB Output is correct
10 Correct 432 ms 4004 KB Output is correct
11 Correct 210 ms 2796 KB Output is correct
12 Correct 424 ms 4092 KB Output is correct
13 Correct 267 ms 3180 KB Output is correct
14 Correct 439 ms 4460 KB Output is correct
15 Execution timed out 4038 ms 58404 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #4
0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4043 ms 56580 KB Time limit exceeded
2 Halted 0 ms 0 KB -