oj.uz

Submission #1090861

# Submission time Handle Problem Language Result Execution time Memory
1090861 2024-09-18T23:19:14 Z vjudge1 Game (IOI13_game) C++17
0 / 100
 13000 ms 348 KB 
#include <bits/stdc++.h>
#include "game.h"
typedef long long ll;
static int R, C;
ll gcd2(ll x, ll y) {
	if (y == 0) return x;
	return gcd2(y, x % y);
}
struct xnod{
	xnod(int tl, int tr):tl(tl),tr(tr),l(NULL),r(NULL),value(0LL) {}
	int tl,tr;
	xnod *l,*r;
	ll value;
};
struct ynod{
	ynod():l(NULL),r(NULL),xst(1,C){}
	ynod *l,*r;
	xnod xst;
} *root;
void init(int r, int c) 
{
	R=r,C=c;
	root=new ynod();
}
void update2(xnod *nod,int q,ll k) {
	int tl=nod->tl,tr=nod->tr,m=(tl+tr)/2;
	if (tl==tr) {
		nod->value=k;
		return;
	}
	xnod** koce=&(q<=m?nod->l:nod->r);
	if (*koce==NULL) {
		*koce=new xnod(q, q);
		(*koce)->value = k;
	} else if ((*koce)->tl <= q && q <= (*koce)->tr) {
		update2(*koce, q, k);
	} else {
		do {
			if (q <= m) tl = m;
			else tr = m + 1;
			m = (tl + tr) >> 1;
		} while ((q <= m) == ((*koce)->tr <= m));
		xnod *temp= new xnod(tl, tr);
		if ((*koce)->tr <= m) temp->l = *koce;
		else temp->r = *koce;
		*koce = temp;
		update2(*koce, q, k);
	}
	nod->value=gcd2(nod->l ? nod->l->value : 0, nod->r?nod->r->value : 0);
}
ll query2(xnod *node,int tl, int tr) {
	if (node == NULL || node->tl > tr || node->tr < tl) return 0;
	if (tl <= node->tl && node->tr <= tr) { return node->value; }
	return gcd2(query2(node->l, tl, tr), query2(node->r, tl, tr));
}

void update1(ynod *node, int tl, int tr, int vx, int vy, ll k) {
	int m = (tl + tr)/2;
	if (tr == tl) {
		update2(&node->xst, vy, k);
		return;
	}
	if (vx <= m) {
		if (node->l == NULL) node->l = new ynod();
		update1(node->l, tl, m, vx, vy, k);
	} else {
		if (node->r == NULL) node->r = new ynod();
		update1(node->r, m + 1, tr, vx, vy, k);
	}
	ll v = gcd2(node->l ? query2(&node->l->xst, vy, vy) : 0,node->r ? query2(&node->r->xst, vy, vy) : 0);
	update2(&node->xst, vy, v);
}

void update(int vx, int vy, ll k) {
	++vx, ++vy;
	update1(root, 1, R, vx, vy, k);
}

ll query1(ynod *node, int tl, int tr, int vxl, int vyl, int vxr, int vyr) {
	if (node == NULL || tl > vxr || tr < vxl) return 0;
	if (vxl <= tl && tr<=vxr) return query2(&node->xst, vyl, vyr);
	int m = (tl+tr)/2;
	return gcd2(query1(node->l, tl, m, vxl, vyl, vxr, vyr),query1(node->r, m + 1, tr, vxl, vyl,vxr,vyr));
}

ll calculate(int vxl, int vyl, int vxr, int vyr) {
	++vxl, ++vyl, ++vxr, ++vyr;
	return query1(root, 1, R, vxl, vyl, vxr, vyr);
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Execution timed out 13090 ms 348 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Execution timed out 13086 ms 348 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Execution timed out 13073 ms 348 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Execution timed out 13039 ms 344 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Execution timed out 13086 ms 348 KB Time limit exceeded
3 Halted 0 ms 0 KB -