Submission #1133359

#	Time	Username	Problem	Language	Result	Execution time	Memory
1133359		siewjh	Game (IOI13_game)	C++20	100 / 100	4473 ms	67408 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
mt19937 mt(26769420);
ll gcd2(ll X, ll Y) {
    ll tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}
struct node{
	int pos, pri; ll val, tval;
	node *l = nullptr, *r = nullptr;
	node (int _pos){
		pos = _pos, pri = mt(), val = tval = 0;
	}
};
ll gettv(node *pt){
	return (pt ? pt->tval : 0);
}
void recalc(node *pt){
	pt->tval = gcd2(pt->val, gcd2(gettv(pt->l), gettv(pt->r)));
}
void split(node *pt, node *&lt, node *&rt, int x){
	if (!pt){
		lt = rt = nullptr; return;
	}
	if (pt->pos <= x){
		split(pt->r, pt->r, rt, x); lt = pt;
	}
	else{
		split(pt->l, lt, pt->l, x); rt = pt;
	}
	recalc(pt);
}
void join(node *&pt, node *lt, node *rt){
	if (!lt){
		pt = rt; return;
	}
	if (!rt){
		pt = lt; return;
	}
	if (lt->pri > rt->pri){
		pt = lt; join(lt->r, lt->r, rt);
	}
	else{
		pt = rt; join(rt->l, lt, rt->l);
	}
	recalc(pt);
}
void upd(node *&pt, int x, ll v){
	node *t1, *t2, *t3;
	split(pt, t1, t3, x); split(t1, t1, t2, x - 1);
	if (!t2) t2 = new node(x);
	t2->val = t2->tval = v;
	join(t1, t1, t2); join(pt, t1, t3);
}
ll qry(node *&pt, int x, int y){
	node *t1, *t2, *t3;
	split(pt, t1, t3, y); split(t1, t1, t2, x - 1);
	ll res = gettv(t2);
	join(t1, t1, t2); join(pt, t1, t3);
	return res;
}
struct node2{
	int s, e, m; node *t;
	node2 *l = nullptr, *r = nullptr;
	node2 (int _s, int _e){
		s = _s, e = _e, m = (s + e) >> 1; t = nullptr;
	}
	void mchild(){
		if (l) return;
		l = new node2(s, m); r = new node2(m + 1, e);
	}
	void upd2(int rp, int cp, ll v){
		if (s == e){
			upd(t, cp, v); return;
		}
		mchild();
		if (rp <= m) l->upd2(rp, cp, v);
		else r->upd2(rp, cp, v);
		upd(t, cp, gcd2(qry(l->t, cp, cp), qry(r->t, cp, cp)));
	}
	ll qry2(int rs, int re, int cs, int ce){
		if (rs == s & re == e) return qry(t, cs, ce);
		if (!l) return 0;
		if (re <= m) return l->qry2(rs, re, cs, ce);
		else if (rs > m) return r->qry2(rs, re, cs, ce);
		else return gcd2(l->qry2(rs, m, cs, ce), r->qry2(m + 1, re, cs, ce));
	}
}*root;
void init(int R, int C) {
    root = new node2(0, R - 1);
}
void update(int P, int Q, ll K) {
    root->upd2(P, Q, K);
}
ll calculate(int P, int Q, int U, int V) {
    return root->qry2(P, U, Q, V);
}

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