Submission #134360

#	Time	Username	Problem	Language	Result	Execution time	Memory
134360		ksmzzang2003	Game (IOI13_game)	C++17	100 / 100	8840 ms	173284 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int R, C, Q;
struct node1d{
	ll val=0;
	int pos=-1;
	node1d *lc=nullptr, *rc=nullptr;
 
	void update(int s, int e, int t, ll v){
		if (e < t || t < s) return;
		if (s == e){
			val = v;
			return;
		}
		int mid = (s+e)/2;
		if (pos>=0){
			if (pos <= mid){
				lc = new node1d;
				lc->pos = pos, lc->val = val;
			}
			else{
				rc = new node1d;
				rc->pos = pos, rc->val = val;
			}
			pos=-1;
		}
		if (t <= mid){
			if (lc == nullptr){
				lc = new node1d;
				lc->pos = t, lc->val = v;
			}
			else lc->update(s, mid, t, v);
		}
		else{
			if (rc == nullptr){
				rc = new node1d;
				rc->pos = t, rc->val = v;
			}
			else rc->update(mid+1, e, t, v);
		}
		val = 0;
		if (lc != nullptr) val = __gcd(val, lc->val);
		if (rc != nullptr) val = __gcd(val, rc->val);
	}
 
	ll query(int s, int e, int ts, int te){
		if (te < s || e < ts) return 0;
		if (ts <= s && e <= te) return val;
		if (pos>=0){
			if (ts <= pos && pos <= te) return val;
			return 0;
		}
		int mid = (s+e)/2;
		ll ret = 0;
		if (lc != nullptr) ret = __gcd(ret, lc->query(s, mid, ts, te));
		if (rc != nullptr) ret = __gcd(ret, rc->query(mid+1, e, ts, te));
		return ret;
	}
};
 
struct node2d{
	node1d *T = new node1d;
	node2d *lc=nullptr, *rc=nullptr;
 
	void update(int s, int e, int tx, int ty, ll v){
		if (e < tx || tx < s) return;
		if (s == e){
			T->update(0, C-1, ty, v);
			return;
		}
		int mid = (s+e)/2;
		if (tx <= mid){
			if (lc == nullptr) lc = new node2d;
			lc->update(s, mid, tx, ty, v);
		}
		else{
			if (rc == nullptr) rc = new node2d;
			rc->update(mid+1, e, tx, ty, v);
		}
		ll ret = 0;
		if (lc != nullptr) ret = __gcd(ret, lc->T->query(0, C-1, ty, ty));
		if (rc != nullptr) ret = __gcd(ret, rc->T->query(0, C-1, ty, ty));
		T->update(0, C-1, ty, ret);
	}
 
	ll query(int s, int e, int txs, int txe, int tys, int tye){
		if (txe < s || e < txs) return 0;
		if (txs <= s && e <= txe) return T->query(0, C-1, tys, tye);
		int mid = (s+e)/2;
		ll ret = 0;
		if (lc != nullptr) ret = __gcd(ret, lc->query(s, mid, txs, txe, tys, tye));
		if (rc != nullptr) ret = __gcd(ret, rc->query(mid+1, e, txs, txe, tys, tye));
		return ret;
	}
} *Seg = new node2d;
 
void init(int r, int c){
	R=r, C=c;
}
 
void update(int x, int y, ll v){
	Seg->update(0, R-1, x, y, v);
}
 
ll calculate(int x1, int y1, int x2, int y2){
	return Seg->query(0, R-1, x1, x2, y1, y2);
}

Compilation message (stderr)

grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^~~

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