Submission #1159624

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159624		WongYiKai	Specijacija (COCI20_specijacija)	C++20	110 / 110	3502 ms	117920 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

struct node {
    int s, e;
    ll mx;
    node *l, *r;
    node (int _s, int _e, ll A[] = NULL): s(_s), e(_e), mx(0), l(NULL), r(NULL) {
        if (A == NULL) return;
        if (s == e) mx = A[s];
        else {
            l = new node(s, (s+e)>>1, A), r = new node((s+e+2)>>1, e, A);
            combine();
        }
    }
    void combine() {
        mx = max(l->mx, r->mx);
    }
    ll range_max(int x, int y) {
        if (s == x && e == y) return mx;
        if (l == NULL) return mx;
        int m = (s+e)>>1;
        if (y <= m) return l->range_max(x, y);
        if (x > m) return r->range_max(x, y);
        return max(l->range_max(x, m), r->range_max(m+1, y));
    }
    ~node() {
        if (l != NULL) delete l;
        if (r != NULL) delete r;
    }
} *root;

struct node2 {
    int s, e;
    ll sum;
    bool lset;
    ll set_val;
    node2 *l, *r;
    node2 (int _s, int _e, int A[] = NULL): s(_s), e(_e), sum(0), lset(0), set_val(0), l(NULL), r(NULL) {
        if (A == NULL) return;
        if (s == e) sum = A[s];
        else {
            l = new node2(s, (s+e)>>1, A), r = new node2((s+e+2)>>1, e, A);
            combine();
        }
    }
    void create_children() {
        if (s == e) return;
        if (l != NULL) return;
        int m = (s+e)>>1;
        l = new node2(s, m);
        r = new node2(m+1, e);
    }
    void self_set(ll v) {
        lset = 1;
        set_val = v;
        sum = v * (e-s+1);
    }
    void lazy_propagate() {
        if (s == e) return;
        if (lset) {
            l->self_set(set_val), r->self_set(set_val);
            lset = set_val = 0;
        }
    }
    void combine() {
        if (l == NULL) return;
        sum = l->sum + r->sum;
    }
    void set(int x, int y, ll v) {
        if (s == x && e == y) { self_set(v); return; }
        int m = (s+e)>>1;
        create_children(); lazy_propagate();
        if (x <= m) l->set(x, min(y, m), v);
        if (y > m) r->set(max(x, m+1), y, v);
        combine();
    }
    ll range_sum(int x, int y) {
        if (s == x && e == y) return sum;
        if (l == NULL || lset) return (sum / (e-s+1)) * (y-x+1);
        int m = (s+e)>>1;
        lazy_propagate();
        if (y <= m) return l->range_sum(x, y);
        if (x > m) return r->range_sum(x, y);
        return l->range_sum(x, m) + r->range_sum(m+1, y);
    }
    ~node2() {
        if (l != NULL) delete l;
        if (r != NULL) delete r;
    }
} *root2;

struct node3 {
    int s, e;
    vector<ll> mst;
    node3 *l, *r;
    node3 (int _s, int _e, ll A[] = NULL): s(_s), e(_e), mst(vector<ll>(0)), l(NULL), r(NULL) {
        if (A == NULL) return;
        if (s == e) mst = vector<ll>(1,A[s]);
        else {
            l = new node3(s, (s+e)>>1, A), r = new node3((s+e+2)>>1, e, A);
            combine();
        }
    }
    void combine() {
        merge(l->mst.begin(),l->mst.end(),r->mst.begin(),r->mst.end(),back_inserter(mst));
    }
    ll query(int x, int y, int v) {
        if (s == x && e == y){
            return mst.end() - upper_bound(mst.begin(),mst.end(), v);
        }
        int m = (s+e)>>1;
        if (y <= m) return l->query(x, y, v);
        if (x > m) return r->query(x, y, v);
        return l->query(x, m, v) + r->query(m+1, y, v);
    }
    ~node3() {
        if (l != NULL) delete l;
        if (r != NULL) delete r;
    }
} *root3;


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

    
	
    ll n,q,t;
    cin >> n >> q >> t;
    ll a[n+5];
    for (int i=0;i<n;i++){
        cin >> a[i];
    }
    //infile.close();

    //cout << q;

    root2 = new node2(0,n+5);
    root2->set(0,n+5,1);
    ll lvl[n+5];
    for (ll i=n-1;i>=0;i--){
        ll target = a[i]-i*(i+1)/2;
        ll l=1,r=n,m;
        while (l<r){
            m = l+(r-l)/2;
            if (root2->range_sum(1,m) < target) l=m+1;
            else r=m;
        }
        lvl[l] = n-i;
        //outfile << target << ' ' << n-i << ' ' << l << "\n";
        root2->set(l,l,0);
    }
    root = new node(1,n,lvl);
    root3 = new node3(1,n,lvl);

    //for (int i=1;i<=n;i++) outfile << lvl[i] << ' ';
    //outfile << "\n";

    //cout << t;

    ll prev = 0;
    while (q--){
        ll x1,y1;
        cin >> x1 >> y1;
        ll x,y;
        x = ((x1-1+t*prev)%((n+1)*(n+2)/2))+1;
        y = ((y1-1+t*prev)%((n+1)*(n+2)/2))+1;
        //cout << x << ' ' << y;
        ll x2=x,y2=y;
        ll cx,cy,rx,ry;
        ll l=1,r=n+1,m;
        while (l<r){
            m = l+(r-l)/2;
            if (m*(m+1)/2 < x) l=m+1;
            else r=m;
        }
        x -= l*(l-1)/2;
        rx = n-l+1;
        l=1,r=n+1;
        while (l<r){
            m = l+(r-l)/2;
            if (m*(m+1)/2 < y) l=m+1;
            else r=m;
        }
        y -= l*(l-1)/2;
        ry = n-l+1;
        l=1,r=n+1;
        while (l<r){
            m = l+(r-l)/2;
            ll pos = 1;
            if (m!=1) pos = root3->query(1,m-1,rx)+1;
            if (pos < x) l=m+1;
            else r=m;
        }
        cx = l;
        l=1,r=n+1;
        while (l<r){
            m = l+(r-l)/2;
            ll pos = 1;
            if (m!=1) pos = root3->query(1,m-1,ry)+1;
            if (pos < y) l=m+1;
            else r=m;
        }
        cy = l;
        if (cx==cy){
            if (rx>=ry){
                cout << x2 << "\n";
                prev = x2;
            }
            else {
                cout << y2 << "\n";
                prev = y2;
            }
            continue;
        }
        ll lca;
        if (cy>cx) lca = root->range_max(cx,cy-1);
        else lca = root->range_max(cy,cx-1);
        if (max(rx,ry) >= lca){
            if (rx>=ry){
                cout << x2 << "\n";
                prev = x2;
            }
            else {
                cout << y2 << "\n";
                prev = y2;
            }
            continue;
        }
        cout << a[n-lca] << "\n";
        prev = a[n-lca];
    }
}

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