Submission #97749

#	Time	Username	Problem	Language	Result	Execution time	Memory
97749		songc	Game (IOI13_game)	C++14	100 / 100	8950 ms	173544 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int R, C, Q;

ll GCD(ll A, ll B){
    if (!B) return A;
    return GCD(B, A%B);
}

struct Node1D{
	ll val=0;
	int pos=-1;
	Node1D *lc=NULL, *rc=NULL;

	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 == NULL){
				lc = new Node1D;
				lc->pos = t, lc->val = v;
			}
			else lc->update(s, mid, t, v);
		}
		else{
			if (rc == NULL){
				rc = new Node1D;
				rc->pos = t, rc->val = v;
			}
			else rc->update(mid+1, e, t, v);
		}
		val = 0;
		if (lc != NULL) val = GCD(val, lc->val);
		if (rc != NULL) 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 != NULL) ret = GCD(ret, lc->query(s, mid, ts, te));
		if (rc != NULL) ret = GCD(ret, rc->query(mid+1, e, ts, te));
		return ret;
	}
};

struct Node2D{
	Node1D *T = new Node1D;
	Node2D *lc=NULL, *rc=NULL;

	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 == NULL) lc = new Node2D;
			lc->update(s, mid, tx, ty, v);
		}
		else{
			if (rc == NULL) rc = new Node2D;
			rc->update(mid+1, e, tx, ty, v);
		}
		ll ret = 0;
		if (lc != NULL) ret = GCD(ret, lc->T->query(0, C-1, ty, ty));
		if (rc != NULL) 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 != NULL) ret = GCD(ret, lc->query(s, mid, txs, txe, tys, tye));
		if (rc != NULL) 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