oj.uz

Submission #378239

# Submission time Handle Problem Language Result Execution time Memory
378239 2021-03-16T10:16:29 Z kartel Specijacija (COCI20_specijacija) C++14
0 / 110
 1314 ms 56556 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;
    }
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:184:13: warning: unused variable 'sd' [-Wunused-variable]
  184 |             sd = getid(root[ny.F], 1, n + 1, ny.S);
      |             ^~
Main.cpp:186:20: warning: unused variable 'r' [-Wunused-variable]
  186 |         int l = 1, r = min(nx.F, ny.F);
      |                    ^

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 221 ms 53612 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 221 ms 53612 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 221 ms 53612 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Incorrect 1314 ms 56556 KB Output isn't correct
2 Halted 0 ms 0 KB -