oj.uz

Submission #377857

# Submission time Handle Problem Language Result Execution time Memory
377857 2021-03-15T11:01:04 Z Vimmer Specijacija (COCI20_specijacija) C++14
0 / 110
 3175 ms 154540 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
{
    ll sum = 0;

    node *l, *r;

    node(): sum(1), l(nullptr), r(nullptr) {}
    node(ll 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(ll tl, ll tr)
{
    if (tl == tr) return new node();
    else
    {
        ll md = (tl + tr) >> 1;

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

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

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

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

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

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

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

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

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

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

vector <ll> vt;

pair <ll, ll> who[N], re[N];

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

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

    l++; r++;

    ll xr = x, yr = y;

    x -= lft(l);

    y -= lft(r);

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

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

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

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

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

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

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

    if (lt == l)
        return xr;

    if (lt == r)
        return yr;

    return a[lt];
}

ll opr(node *v, ll tl, ll tr, ll l, ll r)
{
    if (tl > tr || l > r || tr < l || r < tl) return -1;

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

    if (tl == tr)
        return tl;

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

    ll a = opr(v->l, tl, md, l, r);

    if (a != -1) return a;

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

ordered_set se;

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 = ((n + 1) * (n + 2)) / 2;

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

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

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

    for (ll i = 1; i <= n + 1; i++)
        who[i] = {i, i};

    for (ll i = n; i >= 1; i--)
    {
        pair <ll, ll> pt;

        ll l = a[i] - lft(i), r = a[i] - lft(i) + 1;

        ll dob = se.order_of_key(l);

        ll db = se.order_of_key(r + 1);

        l += dob; r += db;

        pt.F = who[l].F;

        pt.S = who[r].S;

        who[l] = pt;

        re[i] = pt;
//        pri("sad" _ pt.F _ pt.S);

        se.insert(l);
    }

    for (ll i = n; i >= 1; i--)
    {
//        pri("ASD" _ re[i].F _ re[i].S);

        ll ps = opr(vr.back(), 1, n + 1, re[i].F + 1, re[i].S);

//        pri(ps);

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

    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:8: warning:   'll node::sum' [-Wreorder]
   33 |     ll 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
0 / 10.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 30.0

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

Subtask #4
0 / 60.0

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