Submission #1113480

#	Time	Username	Problem	Language	Result	Execution time	Memory
1113480		Gray	Game (IOI13_game)	C++17	63 / 100	1479 ms	256000 KiB

game

#include<bits/stdc++.h>
#include <type_traits>
#include "game.h"
#define ll long long
#define ff first
#define ss second
#define ln "\n"
using namespace std;
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;
		SegTree1D *val;
		int csz;
		mNode(int _csz){
			csz=_csz;
			left=right=nullptr;
			val = new SegTree1D(csz);
		}
		void update(int tl, int tr, int i, int j, ll x){
			if (tl==tr){
				val->update(j, x);
			}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->getval(j):0), (right?right->val->getval(j):0)));
			}
		}
		ll query(int li, int ri, int lj, int rj, int tl, int tr){
			if (tl==li and tr==ri){
				return val->query(lj, rj);
			}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);
}

void update(int P, int Q, long long K) {
	DS.update(P, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
	/* ... */
	return DS.query(P, U, Q, V);
}

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