Submission #437373

#	Time	Username	Problem	Language	Result	Execution time	Memory
437373		Eric_hoo	Game (IOI13_game)	C++14	100 / 100	4413 ms	59476 KiB

game

#include "game.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define W(x) ((x) ? (x)->w : 0)
#define ID(x, y) (((long long)(x) << 30) + (y))
using namespace std;

inline long long gcd(long long x, long long y) {
	while (x && y) {
		if (x > y) x = x % y;
		else y = y % x;
	}
	return x | y;
}

struct Node {
	long long x; long long y, w; int fix;
	int l, r;
	Node *lson, *rson;
	Node() {fix = rand(), lson = rson = NULL;}
	void pushup() {
		w = gcd(y, gcd(W(lson), W(rson))), l = r = (x >> 30);
		if (lson) l = lson->l;
		if (rson) r = rson->r;
	}
}NODEPOOL[700000], *NODECUR = NODEPOOL;

typedef pair <Node *, Node *> pnn;

Node *merge(Node *l, Node *r) {
	if (!l || !r) return l ? l : r;
	if (l->fix > r->fix) {
		l->rson = merge(l->rson, r);
		l->pushup();
		return l;
	} else {
		r->lson = merge(l, r->lson);
		r->pushup();
		return r;
	}
}

pnn split(Node *T, long long x) {
	if (!T) return pnn(NULL, NULL);
	if (x < T->x) {
		pnn t = split(T->lson, x);
		T->lson = t.se, T->pushup();
		return mp(t.fi, T);
	} else {
		pnn t = split(T->rson, x);
		T->rson = t.fi, T->pushup();
		return mp(T, t.se);
	}
}

void Insert(Node *&T, int x, int y, long long w) {
	pnn t1 = split(T, ID(y, x - 1)), t2 = split(t1.se, ID(y, x));
	if (!t2.fi) t2.fi = NODECUR++;
	t2.fi->x = ID(y, x), t2.fi->y = t2.fi->w = w, t2.fi->l = t2.fi->r = y;
	T = merge(t1.fi, merge(t2.fi, t2.se));
}

long long Query(Node *T, const int &l, const int &r) {
	if (!T || T->l > r || T->r < l) return 0;
	if (l <= T->l && T->r <= r) return T->w;
	if ((T->x >> 30) < l) return Query(T->rson, l, r);
	if ((T->x >> 30) > r) return Query(T->lson, l, r);
	return gcd(T->y, gcd(Query(T->lson, l, r), Query(T->rson, l, r)));
}

struct Seg {
	Node *T;
	Seg *lson, *rson;
	Seg() {T = NULL, lson = rson = NULL;}
}SEGPOOL[700000], *SEGCUR = SEGPOOL, *T = NULL;

void Update(Seg *&T, int l, int r, int x, int y, long long w) {
	if (!T) T = SEGCUR++;
	Insert(T->T, x, y, w);
	if (l == r) return ;
	int mid = l + r >> 1;
	if (x <= mid) Update(T->lson, l, mid, x, y, w);
	else Update(T->rson, mid + 1, r, x, y, w);
}

long long Query(Seg *T, int l, int r, int L, int R, int LL, int RR) {
	if (!T) return 0;
	if (l == L && r == R) return Query(T->T, LL, RR);
	int mid = l + r >> 1;
	if (R <= mid) return Query(T->lson, l, mid, L, R, LL, RR);
	if (L > mid) return Query(T->rson, mid + 1, r, L, R, LL, RR);
	return gcd(Query(T->lson, l, mid, L, mid, LL, RR), Query(T->rson, mid + 1, r, mid + 1, R, LL, RR));
}

int N, M, Q;

void read(int &x) {
	char c = getchar(); while (c < '0' || c > '9') c = getchar();
	x = c - '0', c = getchar(); while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
}

void read(long long &x) {
	char c = getchar(); while (c < '0' || c > '9') c = getchar();
	x = c - '0', c = getchar(); while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
}

char st[100];

void print(long long x) {
	int tp = 0;
	if (!x) st[tp++] = '0';
	while (x) st[tp++] = x % 10 + '0', x /= 10;
	while (tp--) putchar(st[tp]);
	putchar('\n');
}

void init(int R, int C) {
	N = R, M = C, srand(2333);
}

void update(int x1, int y1, long long w) {
	x1++, y1++;
	Update(T, 1, N, x1, y1, w);
}

long long calculate(int x1, int x2, int y1, int y2) {
	x1++, x2++, y1++, y2++;
	return Query(T, 1, N, x1, y1, x2, y2);
}

Compilation message (stderr)

game.cpp: In function 'void Update(Seg*&, int, int, int, int, long long int)':
game.cpp:83:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   83 |  int mid = l + r >> 1;
      |            ~~^~~
game.cpp: In function 'long long int Query(Seg*, int, int, int, int, int, int)':
game.cpp:91:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   91 |  int mid = l + r >> 1;
      |            ~~^~~

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