oj.uz

Submission #377900

# Submission time Handle Problem Language Result Execution time Memory
377900 2021-03-15T13:17:55 Z Vimmer Specijacija (COCI20_specijacija) C++14
10 / 110
 4000 ms 135268 KB 
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-O3")
#pragma GCC optimize("Ofast")

#define N 200051
#define NN 1005000
#define PB push_back
#define M ll(1e9 + 7)
#define all(x) x.begin(), x.end()
#define sz(x) int(x.size())
#define pri(x) cout << x << endl
#define endl '\n'
#define _ << " " <<
#define F first
#define S second

using namespace std;
//using namespace __gnu_pbds;

typedef long long ll;
//typedef tree <ll, null_type, less_equal <ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

typedef long double ld;
typedef unsigned long long ull;
typedef short int si;

struct node
{
    int sum = 0;

    node *l, *r;

    node(): sum(1), l(nullptr), r(nullptr) {}
    node(int sm): sum(sm), l(nullptr), r(nullptr) {}

    node(node *lt, node *rt): l(lt), r(rt), sum(lt->sum + rt->sum) {}
};

vector <node*> vr;

node* bld(int tl, int tr)
{
    if (tl == tr) return new node();
    else
    {
        int md = (tl + tr) >> 1;

        return new node(bld(tl, md), bld(md + 1, tr));
    }
}

node* upd(node *v, int tl, int tr, int ps)
{
    if (tl == tr)
    {
        return new node(0);
    }

    int md = (tl + tr) >> 1;

    if (v ->l->sum >= ps)
    {
        return new node(upd(v->l, tl, md, ps), v->r);
    }
    else
    {
        return new node(v->l, upd(v->r, md + 1, tr, ps - v->l->sum));
    }
}

int get(node *v, int tl, int tr, int l, int r)
{
    if (tr < l || r < tl) return 0;

    if (l <= tl && tr <= r)
        return v->sum;

    int md = (tl + tr) >> 1;

    return get(v->l, tl, md, l, r) + get(v->r, md + 1, tr, l, r);
}

int opr(node *v, int tl, int tr, int ps)
{
    if (tl == tr)
        return tl;

    int md = (tl + tr) >> 1;

    if (v->l->sum >= ps)
        return opr(v->l, tl, md, ps);

    return opr(v->r, md + 1, tr, ps - v->l->sum);
}

int n, q, t;
ll a[N];

ll lft(int i) {return 1ll * i * (i - 1) / 2;}

vector <ll> vt;

ll ans(ll x, ll y)
{
    if (x == y)
        return x;

    int l = upper_bound(all(vt), x) - 1 - vt.begin();
    int r = upper_bound(all(vt), y) - 1 - vt.begin();

    l++; r++;

    ll xr = x, yr = y;

    x -= lft(l);

    y -= lft(r);

    x = opr(vr[n + 1 - l], 1, n + 1, x);

    y = opr(vr[n + 1 - r], 1, n + 1, y);

    if (x == y)
        return min(xr, yr);

    if (x > y)
        swap(x, y);

    int lt = 1, rt = min(l, r);

    while (lt < rt)
    {
        int md = (lt + rt + 1) >> 1;

        int sm = get(vr[n - md + 1], 1, n + 1, x, y - 1);

        if (sm == 0)
            lt = md;
                else rt = md - 1;
    }

    return a[lt];
}

int main()
{
    ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0);

//    freopen("1.in", "r", stdin);

    cin >> n >> q >> t;

    ll m = (1ll * (n + 1) * (n + 2)) / 2;

    vr.PB(bld(1, n + 1));

    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];

        vt.PB(lft(i) + 1);
    }

    for (int i = n; i >= 1; i--)
    {
        int l = a[i] - lft(i);

        vr.PB(upd(vr.back(), 1, n + 1, l));

    }

    vt.PB(lft(n + 1) + 1);

    ll lst = 0;

    for (; q > 0; q--)
    {
        ll x, y;

        cin >> x >> y;

        x = (x - 1 + t * lst) % m + 1;

        y = (y - 1 + t * lst) % m + 1;

        lst = ans(x, y);

        pri(lst);
    }
}

Compilation message

Main.cpp: In constructor 'node::node(node*, node*)':
Main.cpp:35:15: warning: 'node::r' will be initialized after [-Wreorder]
   35 |     node *l, *r;
      |               ^
Main.cpp:33:9: warning:   'int node::sum' [-Wreorder]
   33 |     int sum = 0;
      |         ^~~
Main.cpp:40:5: warning:   when initialized here [-Wreorder]
   40 |     node(node *lt, node *rt): l(lt), r(rt), sum(lt->sum + rt->sum) {}
      |     ^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 406 ms 134620 KB Output is correct
2 Correct 23 ms 10344 KB Output is correct
3 Correct 425 ms 134748 KB Output is correct
4 Correct 214 ms 70636 KB Output is correct
5 Correct 410 ms 134748 KB Output is correct
6 Correct 113 ms 40036 KB Output is correct
7 Correct 275 ms 134768 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 406 ms 134620 KB Output is correct
2 Correct 23 ms 10344 KB Output is correct
3 Correct 425 ms 134748 KB Output is correct
4 Correct 214 ms 70636 KB Output is correct
5 Correct 410 ms 134748 KB Output is correct
6 Correct 113 ms 40036 KB Output is correct
7 Correct 275 ms 134768 KB Output is correct
8 Incorrect 399 ms 1300 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 406 ms 134620 KB Output is correct
2 Correct 23 ms 10344 KB Output is correct
3 Correct 425 ms 134748 KB Output is correct
4 Correct 214 ms 70636 KB Output is correct
5 Correct 410 ms 134748 KB Output is correct
6 Correct 113 ms 40036 KB Output is correct
7 Correct 275 ms 134768 KB Output is correct
8 Incorrect 399 ms 1300 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4065 ms 135268 KB Time limit exceeded
2 Halted 0 ms 0 KB -