Submission #380998

#	Time	Username	Problem	Language	Result	Execution time	Memory
380998		ne4eHbKa	Specijacija (COCI20_specijacija)	C++17	10 / 110	1853 ms	149340 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#ifndef _LOCAL
//#pragma GCC optimize("O3,Ofast")
#else
#pragma GCC optimize("O0")
#endif
template<typename t> inline void umin(t &a, const t b) {a = min(a, b);}
template<typename t> inline void umax(t &a, const t b) {a = max(a, b);}
typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
typedef int8_t byte;
ll time() {return chrono::system_clock().now().time_since_epoch().count();}
mt19937 rnd(time());
#define ft first
#define sd second
#define len(f) int((f).size())
#define bnd(f) (f).begin(), (f).end()
#define _ <<' '<<
#define int ll
const int inf = 1e9 + 5;
const ll inf64 = 4e18 + 5;
const int md = 998244353;
namespace MD {
    void add(int &a, const int b) {if((a += b) >= md) a -= md;}
    void sub(int &a, const int b) {if((a -= b) < 0) a += md;}
    int prod(const int a, const int b) {return ll(a) * b % md;}
};

int n, q, T;
const int N = 2e5 + 5;
ll a[N], b[N], t[N], z;

struct tree {
    tree *l, *r;
    int v;
    tree(int tl = 0, int tr = n - 1) {
        if(tl < 0) {
            l = r = 0;
            v = 0;
        } else if(tl < tr) {
            int tm = tl + tr >> 1;
            l = new tree(tl, tm);
            r = new tree(tm + 1, tr);
            v = l->v + r->v;
        } else {
            l = r = 0;
            v = 1;
        }
    }
    tree(const tree *f) {memcpy(this, f, sizeof *f);}
    tree *upd(int i, int tl = 0, int tr = n - 1) const {
        if(tl == tr) return new tree(-1);
        int tm = tl + tr >> 1;
        tree *res = new tree(this);
        if(i <= tm)
            res->l = l->upd(i, tl, tm);
        else
            res->r = r->upd(i, tm + 1, tr);
        res->v--;
        return res;
    }
    int kth(int k, int tl = 0, int tr = n - 1) const {
        if(tl == tr) return tl;
        int tm = tl + tr >> 1;
        return l->v > k
            ? l->kth(k, tl, tm)
            : r->kth(k - l->v, tm + 1, tr);
    }
    int sum(int R, int tl = 0, int tr = n - 1) const {
        if(tr <= R) return v;
        if(tl > R) return 0;
        int tm = tl + tr >> 1;
        return l->sum(R, tl, tm) +
               r->sum(R, tm + 1, tr);
    }
};

vector<tree*> p;

void get(ll &x, int &i, int &j) {
    cin >> x;
    x = 1 + (x - 1 + T * z) % ((n + 1) * ll(n) >> 1);
    i = upper_bound(b, b + n, x) - b - 1;
    j = p[i]->kth(x - b[i]);
}

struct tree2 {
    tree2 *l, *r;
    int v;
    tree2(int tl = 0, int tr = n - 2) {
        if(tl < tr) {
            int tm = tl + tr >> 1;
            l = new tree2(tl, tm);
            r = new tree2(tm + 1, tr);
            v = min(l->v, r->v);
        } else {
            l = r = 0;
            v = t[tl];
        }
    }
    int get(int L, int R, int tl = 0, int tr = n - 2) const {
        if(L > R) return +inf;
        if(L == tl && R == tr) return v;
        int tm = tl + tr >> 1;
        return min(l->get(L, min(R, tm), tl, tm),
                   r->get(max(tm + 1, L), R, tm + 1, tr));
    }
};

void solve() {
    cin >> n >> q >> T; ++n;
    for(ll i = 0, j = 1; i < n; ++i) {
        j += i;
        if(i + 1 < n)
            cin >> a[i],
            a[i] -= j;
        b[i] = j;
    }
    p.assign(1, new tree());
    for(int i = n - 2; ~i; --i) {
        tree *rt = p.back();
        int c = rt->kth(a[i]);
        p.push_back(rt = rt->upd(c));
        t[c] = i;
    }
    reverse(bnd(p));
    tree2 tt {};
    z = 0;
    for(int i = 0; i < q; ++i) {
        ll x, y;
        int ix, iy, jx, jy;
        get(x, ix, jx);
        get(y, iy, jy);
        if(jx == jy) {
            z = ix < iy ? x : y;
        } else {
            int le = min(jx, jy);
            int ri = max(jx, jy);
            int v = tt.get(le, ri - 1);
            assert(p[v]->sum(le) == p[v]->sum(le - 1));
            z = b[v] + p[v]->sum(le);
        }
        cout << z << '\n';
    }
}

signed main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#ifndef _LOCAL
//    freopen("file.in", "r", stdin);
//    freopen("file.out", "w", stdout);
#else
    system("color a");
    freopen("in.txt", "r", stdin);
    int t; cin >> t;
    while(t--)
#endif
    solve();
}

Compilation message (stderr)

Main.cpp: In constructor 'tree::tree(ll, ll)':
Main.cpp:43:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |             int tm = tl + tr >> 1;
      |                      ~~~^~~~
Main.cpp: In member function 'tree* tree::upd(ll, ll, ll) const':
Main.cpp:55:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   55 |         int tm = tl + tr >> 1;
      |                  ~~~^~~~
Main.cpp: In member function 'll tree::kth(ll, ll, ll) const':
Main.cpp:66:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   66 |         int tm = tl + tr >> 1;
      |                  ~~~^~~~
Main.cpp: In member function 'll tree::sum(ll, ll, ll) const':
Main.cpp:74:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   74 |         int tm = tl + tr >> 1;
      |                  ~~~^~~~
Main.cpp: In constructor 'tree2::tree2(ll, ll)':
Main.cpp:94:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   94 |             int tm = tl + tr >> 1;
      |                      ~~~^~~~
Main.cpp: In member function 'll tree2::get(ll, ll, ll, ll) const':
Main.cpp:106:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  106 |         int tm = tl + tr >> 1;
      |                  ~~~^~~~

• Subtask 1: 10 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 30
• Subtask 4: 0 / 60