Submission #1289079

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289079		minhjulzi	Specijacija (COCI20_specijacija)	C++17	110 / 110	835 ms	249292 KiB

Main

#include <bits/stdc++.h>
using namespace std;
bool M1;

#define task "task"
#define bit(x, i) ((x >> i) & 1)

// https://trap.jp/post/1224/
#define FOR1(i, a, b) for(int i = (a), _b = (b); i <= _b; i ++)
#define FOR2(i, a, b, c) for(int i = (a), _b = (b); i <= _b; i += c)
#define FORD1(i, a, b) for(int i = (a), _b = (b); i >= _b; i --)
#define FORD2(i, a, b, c) for(int i = (a), _b = (b); i >= _b; i -= c)
#define overload4(a, b, c, d, name, ...) name
#define FOR(...) overload4(__VA_ARGS__, FOR2, FOR1)(__VA_ARGS__)
#define FORD(...) overload4(__VA_ARGS__, FORD2, FORD1)(__VA_ARGS__)

#define pb emplace_back
#define pf emplace_front
#define ins emplace
#define mp make_pair
#define fi first
#define se second

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
// mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
// ll rand(ll l, ll r) { assert(l <= r); return uniform_int_distribution<ll>(l, r)(rd); }
const int N = 2e5 + 5;
const ll inf = 1e18;
const int mod = 1e9 + 7;
const int base = 31;
int n, q, t;
ll a[N], bottom[2 * N];
int root[N];
struct PersistentSegmentTree{
    #define lc st[id].l
    #define rc st[id].r
    int n;
    struct Node{
        int id, sz, l, r;
    } st[3 * 21 * N];
    int cur = 0;
    void init(int _n){
        n = _n;
    }
    int update(int pre, int l, int r, int pos, int val){
        int id = ++ cur;
        st[id] = st[pre];
        if(l == r){
            st[id].sz = (val > 0);
            st[id].id = val;
            return id;
        }
        int mid = l + r >> 1;
        if(pos <= mid){
            rc = st[pre].r;
            lc = update(st[pre].l, l, mid, pos, val);
        }
        else{
            lc = st[pre].l;
            rc = update(st[pre].r, mid + 1, r, pos, val);
        }
        st[id].sz = st[lc].sz + st[rc].sz;
        return id;
    }
    pii query(int id, int l, int r, int k){
        if(l == r) return {l, st[id].id};
        int mid = l + r >> 1;
        int cnt = st[lc].sz;
        if(k > cnt) return query(rc, mid + 1, r, k - cnt);
        else return query(lc, l, mid, k);
    }
    void upd(int v, int pos, int val){
        root[v] = update(root[v], 1, n, pos, val);
    }
    pii get(int v, int k){
        return query(root[v], 1, n, k);
    }
} pst;
int ver = 1;
int h[2 * N], par[2 * N][20];
vector<int> g[2 * N];
void dfs(int u, int p){
    par[u][0] = p;
    FOR(i, 1, 19) par[u][i] = par[par[u][i - 1]][i - 1];
    for(int v : g[u]) if(v != p){
        h[v] = h[u] + 1;
        dfs(v, u);
    }
}
int lca(int u, int v){
    if(h[u] < h[v]) swap(u, v);
    FORD(i, 19, 0) if(h[par[u][i]] >= h[v]) u = par[u][i];
    if(u == v) return u;
    FORD(i, 19, 0) if(par[u][i] != par[v][i]) u = par[u][i], v = par[v][i];
    return par[u][0];
}
ll getfl(ll x){
    ll i = sqrt(2 * x);
    while(i * (i + 1) / 2 < x) ++i;
    while(i * (i - 1) / 2 >= x) --i;
    return i;
}
ll calc(ll x, ll y){
    ll idx = getfl(x), idy = getfl(y);
    int posx = x - 1ll * idx * (idx - 1) / 2, posy = y - 1ll * idy * (idy - 1) / 2;
    int compx = pst.get(idx, posx).se, comy = pst.get(idy, posy).se;
    int p = lca(compx, comy);
    return min({x, y, bottom[p]});
}
void solve(){
    cin>>n>>q>>t;
    FOR(i, 1, n) cin>>a[i];
    pst.init(n + 1);
    FOR(i, 1, n + 1){
        bottom[i] = 1ll * n * (n + 1) / 2 + i;
        pst.upd(n + 1, i, i);
    }
    int comp = n + 1;
    FORD(i, n, 1){
        int idx = 1ll * a[i] - 1ll * i * (i - 1) / 2;
        pii l = pst.get(i + 1, idx), r = pst.get(i + 1, idx + 1);
        bottom[++comp] = a[i];
        g[comp].pb(l.se);
        g[l.se].pb(comp);
        g[comp].pb(r.se);
        g[r.se].pb(comp);
        root[i] = pst.update(root[i + 1], 1, n + 1, l.fi, comp);
        root[i] = pst.update(root[i], 1, n + 1, r.fi, 0);
    }
    dfs(comp, 0);
    h[0] = -1;
    ll ans = 0;
    while(q --){
        ll x, y; cin>>x>>y;
        x = (x - 1 + 1ll * t * ans) % (1ll * (n + 1) * (n + 2) / 2) + 1;
        y = (y - 1 + 1ll * t * ans) % (1ll * (n + 1) * (n + 2) / 2) + 1;
        ans = calc(x, y);
        cout<<ans<<'\n';
    }
}
bool M2;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    if(fopen(task".inp", "r")){
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    int tc = 1;
    // cin>>tc;
    while(tc --) solve();
    cerr << "\nMemory: " << abs(&M2-&M1)/1024.0/1024 << " Mb\n";
    cerr << "\nTime: " << 1.0 * clock() / CLOCKS_PER_SEC << " ms\n";
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:150:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  150 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:151:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  151 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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