Submission #1068447

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1068447	2024-08-21T09:55:07 Z	GrindMachine	Game (IOI13_game)	C++17	100 / 100	6185 ms	141996 KB

game

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a,b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a,b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

/*

already knew the solution idea (dynamic segtree with a treap in each node)

*/

const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

#include "game.h"

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

struct node{
    node *l = nullptr, *r = nullptr;
    int siz = 0;
    unsigned int prior = 0;
    bool flip = 0;
    pii p = {0,0}, mxp = {0,0};
    ll val = 0, g = 0;

    node(int i, int j, ll v){
        l = r = nullptr;
        siz = 1;
        prior = rng();
        flip = 0;
        p = mxp = {i,j};
        val = v, g = v;
    }
 
    void recalc(){
        siz = 1, mxp = p, g = val;
        if(l) siz += l->siz, amax(mxp,l->mxp), g = gcd(g,l->g);
        if(r) siz += r->siz, amax(mxp,r->mxp), g = gcd(g,r->g);
    }

    void prop(){
        if(!flip) return;
        swap(l,r);
        if(l) l->flip ^= 1;
        if(r) r->flip ^= 1;
        flip = 0;
    }
 
    ~node(){
        delete l;
        delete r;
        l = r = nullptr;
    }
};
 
node* merge(node* u, node* v){
    if(u) u->prop();
    if(v) v->prop();
 
    if(u == nullptr) return v;
    if(v == nullptr) return u;
 
    if(u->prior > v->prior){
        // v goes to u's right subtree
        u->r = merge(u->r,v);
        u->recalc();
        return u;
    }
    else{
        // u goes to v's left subtree
        v->l = merge(u,v->l);
        v->recalc();
        return v;
    }
}

pair<node*,node*> split(node* u, int k){
    if(!u) return {nullptr,nullptr};
 
    u->prop();
 
    if(k == 0) return {nullptr,u};
    if(k == u->siz) return {u,nullptr};
 
    int pos = 1;
    if(u->l) pos += u->l->siz;
 
    if(k < pos){
        // required pos lies in the left subtree
        // root belongs to the right subtree
        auto p = split(u->l,k);
        u->l = p.ss;
        u->recalc();
        return {p.ff,u};
    }
    else{
        // required pos lies in the right subtree
        // root belongs to the left subtree
        auto p = split(u->r,k-pos);
        u->r = p.ff;
        u->recalc();
        return {u,p.ss};
    }
}

int ub(node* u, pii i){
    // first ind s.t pos > i (inds start from 1)
    if(u->l and u->l->mxp > i){
        return ub(u->l,i);
    }

    int add = (u->l?u->l->siz:0);

    if(u->p > i){
        return add+1;
    }

    if(u->r){
        return ub(u->r,i)+add+1;
    }
    else{
        return add+2;
    }
}

vector<node*> split_many(node* treap, vector<int> cuts){
    vector<node*> parts;
    rev(i,sz(cuts)-1,0){
        auto p = split(treap,cuts[i]);
        treap = p.ff;
        parts.pb(p.ss);
    }
 
    parts.pb(treap);
    reverse(all(parts));
    return parts;
}
 
node* merge_many(vector<node*> parts){
    node* treap = nullptr;
    trav(part,parts){
        treap = merge(treap,part);
    }
    return treap;
}

struct dynamic_treap{
    node* treap = new node(0,0,0);
    
    void pupd(int i, int j, ll v){
        pii px = {i,j};
        int pos = ub(treap,px);
        auto parts = split_many(treap,{pos-1});

        if(parts[0] and parts[0]->mxp == px){
            auto new_parts = split_many(parts[0],{parts[0]->siz-1});
            parts[0] = new_parts[0];
        }

        parts.insert(parts.begin()+1,new node(i,j,v));    
        treap = merge_many(parts);
    }   

    ll query(int l, int r){
        l = ub(treap,{l,-1});
        r = ub(treap,{r+1,-1})-1;
        if(l > r) return 0ll;
        auto parts = split_many(treap,{l-1,r});
        ll res = parts[1]->g;
        treap = merge_many(parts);
        return res;
    }
};

struct dynamic_segtree{
    struct node{
        node *l = nullptr, *r = nullptr;
        dynamic_treap treap;
        node(){

        }
    };

    node* root;
    int n;

    dynamic_segtree(){

    }

    dynamic_segtree(int n_){
        root = new node();
        n = n_;
    }

    void pupd(node* &u, int lx, int rx, int i, int j, ll v){
        u->treap.pupd(j,i,v);
        if(rx-lx == 1) return;

        int mid = (lx+rx) >> 1;

        if(!u->l) u->l = new node();
        if(!u->r) u->r = new node();

        if(i < mid){
            pupd(u->l,lx,mid,i,j,v);
        }
        else{
            pupd(u->r,mid,rx,i,j,v);
        }
    }

    void pupd(int i, int j, ll v){
        pupd(root,0,n,i,j,v);
    }

    ll query(node* u, int lx, int rx, int l, int r, int x, int y){
        if(!u) return 0;
        if(lx >= r or rx <= l) return 0;
        if(lx >= l and rx <= r) return u->treap.query(x,y);
        
        int mid = (lx+rx) >> 1;
        return gcd(query(u->l,lx,mid,l,r,x,y),query(u->r,mid,rx,l,r,x,y));
    }

    ll query(int l, int r, int x, int y){
        return query(root,0,n,l,r+1,x,y);
    }
};

dynamic_segtree st;

void init(int n, int m) {
    st = dynamic_segtree(n);
}

void update(int i, int j, long long v) {
    st.pupd(i,j,v);
}

long long calculate(int l1, int l2, int r1, int r2) {
    return st.query(l1,r1,l2,r2);
}

Subtask #1

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct

Subtask #2

27.0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	344 KB	Output is correct
4	Correct	755 ms	11700 KB	Output is correct
5	Correct	351 ms	12152 KB	Output is correct
6	Correct	806 ms	9488 KB	Output is correct
7	Correct	965 ms	9156 KB	Output is correct
8	Correct	611 ms	7700 KB	Output is correct
9	Correct	947 ms	9296 KB	Output is correct
10	Correct	854 ms	8896 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct

Subtask #3

26.0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	1 ms	344 KB	Output is correct
7	Correct	0 ms	600 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	1443 ms	16952 KB	Output is correct
13	Correct	2681 ms	13756 KB	Output is correct
14	Correct	452 ms	14932 KB	Output is correct
15	Correct	2754 ms	15180 KB	Output is correct
16	Correct	207 ms	14944 KB	Output is correct
17	Correct	1394 ms	11464 KB	Output is correct
18	Correct	2482 ms	16468 KB	Output is correct
19	Correct	2082 ms	16632 KB	Output is correct
20	Correct	1924 ms	16020 KB	Output is correct
21	Correct	0 ms	348 KB	Output is correct

Subtask #4

17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 ms	500 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Correct	788 ms	11860 KB	Output is correct
13	Correct	379 ms	11968 KB	Output is correct
14	Correct	808 ms	9352 KB	Output is correct
15	Correct	951 ms	9300 KB	Output is correct
16	Correct	620 ms	7852 KB	Output is correct
17	Correct	918 ms	9296 KB	Output is correct
18	Correct	789 ms	9040 KB	Output is correct
19	Correct	1383 ms	17232 KB	Output is correct
20	Correct	2648 ms	13704 KB	Output is correct
21	Correct	446 ms	14956 KB	Output is correct
22	Correct	2814 ms	15184 KB	Output is correct
23	Correct	213 ms	15332 KB	Output is correct
24	Correct	1422 ms	11344 KB	Output is correct
25	Correct	2438 ms	16496 KB	Output is correct
26	Correct	2080 ms	16720 KB	Output is correct
27	Correct	1947 ms	16016 KB	Output is correct
28	Correct	721 ms	72276 KB	Output is correct
29	Correct	1958 ms	75088 KB	Output is correct
30	Correct	3989 ms	52304 KB	Output is correct
31	Correct	3569 ms	47836 KB	Output is correct
32	Correct	780 ms	34196 KB	Output is correct
33	Correct	1121 ms	34644 KB	Output is correct
34	Correct	288 ms	68796 KB	Output is correct
35	Correct	1710 ms	42720 KB	Output is correct
36	Correct	3004 ms	72936 KB	Output is correct
37	Correct	2429 ms	73156 KB	Output is correct
38	Correct	2346 ms	72528 KB	Output is correct
39	Correct	2059 ms	58896 KB	Output is correct
40	Correct	1 ms	344 KB	Output is correct

Subtask #5

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	1 ms	504 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	765 ms	11936 KB	Output is correct
13	Correct	334 ms	12116 KB	Output is correct
14	Correct	817 ms	9552 KB	Output is correct
15	Correct	950 ms	9312 KB	Output is correct
16	Correct	644 ms	7764 KB	Output is correct
17	Correct	921 ms	9188 KB	Output is correct
18	Correct	802 ms	8912 KB	Output is correct
19	Correct	1396 ms	17380 KB	Output is correct
20	Correct	2649 ms	13684 KB	Output is correct
21	Correct	448 ms	14928 KB	Output is correct
22	Correct	2951 ms	15332 KB	Output is correct
23	Correct	219 ms	15184 KB	Output is correct
24	Correct	1411 ms	11348 KB	Output is correct
25	Correct	2562 ms	16468 KB	Output is correct
26	Correct	2158 ms	16724 KB	Output is correct
27	Correct	2005 ms	16168 KB	Output is correct
28	Correct	815 ms	72368 KB	Output is correct
29	Correct	1992 ms	74936 KB	Output is correct
30	Correct	4260 ms	52296 KB	Output is correct
31	Correct	3548 ms	47748 KB	Output is correct
32	Correct	756 ms	34384 KB	Output is correct
33	Correct	1090 ms	34716 KB	Output is correct
34	Correct	287 ms	68692 KB	Output is correct
35	Correct	1692 ms	42576 KB	Output is correct
36	Correct	3031 ms	72884 KB	Output is correct
37	Correct	2487 ms	73024 KB	Output is correct
38	Correct	2321 ms	72588 KB	Output is correct
39	Correct	970 ms	140068 KB	Output is correct
40	Correct	3021 ms	141996 KB	Output is correct
41	Correct	6185 ms	103040 KB	Output is correct
42	Correct	5361 ms	93140 KB	Output is correct
43	Correct	541 ms	136788 KB	Output is correct
44	Correct	1301 ms	63704 KB	Output is correct
45	Correct	2091 ms	58864 KB	Output is correct
46	Correct	3746 ms	140880 KB	Output is correct
47	Correct	3729 ms	140804 KB	Output is correct
48	Correct	3481 ms	140384 KB	Output is correct
49	Correct	1 ms	348 KB	Output is correct