Submission #1113707

#	Time	Username	Problem	Language	Result	Execution time	Memory
1113707		Gray	Game (IOI13_game)	C++17	100 / 100	5952 ms	107592 KiB

game

#include<bits/stdc++.h>
#include <random>
#include "game.h"
#define ll long long
#define ff first
#define ss second
#define ln "\n"
using namespace std;
mt19937 mt(time(nullptr));
struct Treap{
    struct Node{
        Node *left, *right;
        ll x, y, gcd, fgcd;
        Node(ll _x, ll _gcd){
            left=right=nullptr;
            x=_x; gcd=fgcd=_gcd;
            y=mt();
        }
        Node(ll _x, ll _y, ll _gcd){
            left=right=NULL;
            x=_x; y=_y; gcd=fgcd=_gcd;
        }
    };
    Node * root;
    Treap(){
        root=new Node(-1, 2e18, 0);
    }
    void upd(Node * t){
        if (!t) return;
        t->fgcd=t->gcd;
        if (t->left) t->fgcd=__gcd(t->left->fgcd, t->fgcd);
        if (t->right) t->fgcd=__gcd(t->right->fgcd, t->fgcd);
    }
    void split(Node *par, Node*&wl, Node*&wr, ll x){
        if (!par){
            wl=wr=nullptr;
        }else if (par->x<=x){
            split(par->right, par->right, wr, x); wl=par;
        }else{
            split(par->left, wl, par->left, x); wr=par;
        }
        upd(wl); upd(wr);
    }
    void merge(Node *& npar, Node *l, Node *r){
        if (!l or !r){
            npar=l?l:r;
        }else if (l->y>r->y){
            merge(l->right, l->right, r); npar=l;
        }else{
            merge(r->left, l, r->left); npar=r;
        }
        upd(npar);
    }
    void insert(Node *& cur, Node * item){
        if (!cur){
            cur=item;
        }else if (cur->y>=item->y){
            insert(cur->x<=item->x?cur->right:cur->left, item);
        }else{
            split(cur, item->left, item->right, item->x); cur=item;
        }
        upd(cur);
    }
    ll query_range(Node *& cur, ll l, ll r){
        Node * t1, * t2, * t3;
        split(cur, t1, t2, l-1);
        split(t2, t2, t3, r);
        ll res=t2?t2->fgcd:0;
        merge(cur, t1, t2);
        merge(cur, cur, t3);
        return res;
    }
    void update(Node * cur, ll x, ll newval){
        if (!cur){
            insert(root, new Node(x, newval));
            return;
        }else if (cur->x==x){
            cur->gcd=newval;
        }else if (cur->x<x){
            update(cur->right, x, newval);
        }else{
            update(cur->left, x, newval);
        }
        upd(cur);
    }
    void update(ll x, ll newval){
        update(root, x, newval);
    }
    void insert(ll x, ll val){
        insert(root, new Node(x, val));
    }
    ll query(ll l, ll r){
        return query_range(root, l, r);
    }
};

// struct SegTree1D{
// 	struct Node{
// 		ll left, right, val;
// 		Node(){
// 			left=right=-1;
// 			val=0;
// 		}
// 	};
// 	vector<Node> nodes;
// 	ll add_node(){
// 	    nodes.push_back(Node());
// 		return nodes.size()-1;
// 	}
// 	map<int, ll> leaves;
// 	int rsz;
// 	SegTree1D(int N){
// 		rsz=N;
// 		add_node();
// 	}
// 	void update(ll tl, ll tr, ll v, ll i, ll x){
// 	    if (tl==tr){
// 			nodes[v].val=x;
// 			leaves[tl]=v;
// 		}else{
// 		    ll tm = (tl+tr)/2;
// 			if (i<=tm){
// 			    if (nodes[v].left==-1) nodes[v].left=add_node();
// 				update(tl, tm, nodes[v].left, i, x);
// 			}else{
// 			    if (nodes[v].right==-1) nodes[v].right=add_node();
// 				update(tm+1, tr, nodes[v].right, i, x);
// 			}
// 			nodes[v].val=0;
// 			if (nodes[v].left!=-1) nodes[v].val=__gcd(nodes[nodes[v].left].val, nodes[v].val);
// 			if (nodes[v].right!=-1) nodes[v].val=__gcd(nodes[nodes[v].right].val, nodes[v].val);
// 		}
// 	}
// 	void update(ll i, ll x){
// 	   update(0, rsz-1, 0, i, x);
// 	}
// 	ll query(ll tl, ll tr, ll v, ll l, ll r){
// 	    if (tl==l and tr==r){
// 			return nodes[v].val;
// 		}
// 		else if (l>r) return 0;
// 		else{
// 		    ll tm = (tl+tr)/2;
// 			ll res=0;
// 			if (nodes[v].left!=-1) res=__gcd(res, query(tl, tm, nodes[v].left, l, min(r, tm)));
// 			if (nodes[v].right!=-1) res=__gcd(res, query(tm+1, tr, nodes[v].right, max(l, tm+1), r));
// 			return res;
// 		}
// 	}
// 	ll query(int l, int r){
// 		return query(0, rsz-1, 0, l, r);
// 	}
// 	ll getval(int ind){
// 		if (!leaves.count(ind)) return 0;
// 		return nodes[leaves[ind]].val;
// 	}
// };
struct SegTree2D{
	struct mNode{
		mNode *left, *right;
		Treap *val;
		int csz;
		mNode(int _csz){
			csz=_csz;
			left=right=nullptr;
			val = new Treap();
		}
		void update(int tl, int tr, int i, int j, ll x){
			if (tl==tr){
			    // cout << "Entered" << endl;
				val->update(j, x);
				// cout << "Exited"<< endl;
			}else{
				int tm = (tl+tr)/2;
				if (i<=tm){
					if (!left) left=new mNode(csz);
					left->update(tl, tm, i, j, x);
				}else{
					if (!right) right=new mNode(csz);
					right->update(tm+1, tr, i, j, x);
				}
				val->update(j, __gcd((left?left->val->query(j, j):0), (right?right->val->query(j, j):0)));
			}
		}
		ll query(int li, int ri, int lj, int rj, int tl, int tr){
			if (tl==li and tr==ri){
			    // cout << lj << "-" << rj << endl;
				ll res= val->query(lj, rj);
				// cout << "Success" << endl;
				return res;
			}else if (li>ri) return 0;
			else{
				ll ret=0;
				int tm = (tl+tr)/2;
				if (left and li<=min(ri, tm)) ret=__gcd(ret, left->query(li, min(ri, tm), lj, rj, tl, tm));
				if (right and max(li, tm+1)<=ri) ret=__gcd(ret, right->query(max(li, tm+1), ri, lj, rj, tm+1, tr));
				return ret;
			}
		}
	};
	mNode * root;
	ll csz, rsz;
	void init(int R, int C){
		rsz=R; csz=C;
		root = new mNode(csz);
	}
	void update(int i, int j, ll x){
		root->update(0, rsz-1, i, j, x);
	}
	ll query(int li, int ri, int lj, int rj){
		return root->query(li, ri, lj, rj, 0, rsz-1);
	}
} DS;


void init(int R, int C) {
	DS.init(R, C);
	// cout << "Init" << endl;
}

void update(int P, int Q, long long K) {
    // cout << "Updating " << P << "-" << Q << "-" << K << endl;
	DS.update(P, Q, K);
	// cout << "Updated " << P << "-" << Q << "-" << K << endl;
}

long long calculate(int P, int Q, int U, int V) {
	/* ... */
	ll res= DS.query(P, U, Q, V);
	// cout << "Queried" << endl;
	return res;
	// return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 27 / 27
• Subtask 3: 26 / 26
• Subtask 4: 17 / 17
• Subtask 5: 20 / 20