oj.uz

Submission #97749

# Submission time Handle Problem Language Result Execution time Memory
97749 2019-02-18T07:51:10 Z songc Game (IOI13_game) C++14
100 / 100
 8950 ms 173544 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 2 ms 256 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 128 KB Output is correct
3 Correct 3 ms 256 KB Output is correct
4 Correct 879 ms 9464 KB Output is correct
5 Correct 539 ms 9920 KB Output is correct
6 Correct 826 ms 6776 KB Output is correct
7 Correct 1153 ms 6264 KB Output is correct
8 Correct 589 ms 4456 KB Output is correct
9 Correct 1010 ms 6392 KB Output is correct
10 Correct 889 ms 6012 KB Output is correct
11 Correct 2 ms 256 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 6 ms 428 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 1592 ms 13128 KB Output is correct
13 Correct 2781 ms 7164 KB Output is correct
14 Correct 392 ms 1400 KB Output is correct
15 Correct 3064 ms 9480 KB Output is correct
16 Correct 335 ms 12008 KB Output is correct
17 Correct 1425 ms 7492 KB Output is correct
18 Correct 2653 ms 12508 KB Output is correct
19 Correct 2476 ms 13300 KB Output is correct
20 Correct 2080 ms 12736 KB Output is correct
21 Correct 2 ms 384 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 944 ms 9456 KB Output is correct
13 Correct 532 ms 9640 KB Output is correct
14 Correct 775 ms 6420 KB Output is correct
15 Correct 907 ms 6320 KB Output is correct
16 Correct 526 ms 4472 KB Output is correct
17 Correct 978 ms 6396 KB Output is correct
18 Correct 886 ms 5852 KB Output is correct
19 Correct 1567 ms 13024 KB Output is correct
20 Correct 2702 ms 7124 KB Output is correct
21 Correct 425 ms 1184 KB Output is correct
22 Correct 3190 ms 9472 KB Output is correct
23 Correct 338 ms 11996 KB Output is correct
24 Correct 1476 ms 7292 KB Output is correct
25 Correct 3110 ms 12324 KB Output is correct
26 Correct 2300 ms 13476 KB Output is correct
27 Correct 2333 ms 12972 KB Output is correct
28 Correct 999 ms 56180 KB Output is correct
29 Correct 2357 ms 51260 KB Output is correct
30 Correct 6732 ms 48224 KB Output is correct
31 Correct 6488 ms 87444 KB Output is correct
32 Correct 976 ms 11000 KB Output is correct
33 Correct 1233 ms 14548 KB Output is correct
34 Correct 542 ms 44828 KB Output is correct
35 Correct 2206 ms 29852 KB Output is correct
36 Correct 4112 ms 49148 KB Output is correct
37 Correct 3259 ms 49344 KB Output is correct
38 Correct 3143 ms 48716 KB Output is correct
39 Correct 2493 ms 40144 KB Output is correct
40 Correct 2 ms 256 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 3 ms 256 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 819 ms 9848 KB Output is correct
13 Correct 546 ms 9848 KB Output is correct
14 Correct 774 ms 6716 KB Output is correct
15 Correct 1060 ms 6448 KB Output is correct
16 Correct 569 ms 4728 KB Output is correct
17 Correct 938 ms 6556 KB Output is correct
18 Correct 852 ms 6436 KB Output is correct
19 Correct 1489 ms 13432 KB Output is correct
20 Correct 2762 ms 7312 KB Output is correct
21 Correct 389 ms 1552 KB Output is correct
22 Correct 3139 ms 9432 KB Output is correct
23 Correct 332 ms 11932 KB Output is correct
24 Correct 1564 ms 7628 KB Output is correct
25 Correct 3114 ms 12644 KB Output is correct
26 Correct 2237 ms 13560 KB Output is correct
27 Correct 2321 ms 12908 KB Output is correct
28 Correct 901 ms 56032 KB Output is correct
29 Correct 2200 ms 51128 KB Output is correct
30 Correct 6965 ms 48136 KB Output is correct
31 Correct 6155 ms 87632 KB Output is correct
32 Correct 1012 ms 10760 KB Output is correct
33 Correct 1273 ms 14472 KB Output is correct
34 Correct 470 ms 44792 KB Output is correct
35 Correct 1821 ms 29964 KB Output is correct
36 Correct 4141 ms 49088 KB Output is correct
37 Correct 3119 ms 49440 KB Output is correct
38 Correct 3005 ms 48788 KB Output is correct
39 Correct 1344 ms 111144 KB Output is correct
40 Correct 3850 ms 94804 KB Output is correct
41 Correct 8760 ms 95568 KB Output is correct
42 Correct 8950 ms 173544 KB Output is correct
43 Correct 952 ms 89464 KB Output is correct
44 Correct 1208 ms 11384 KB Output is correct
45 Correct 2693 ms 40180 KB Output is correct
46 Correct 5179 ms 93564 KB Output is correct
47 Correct 5183 ms 93792 KB Output is correct
48 Correct 5183 ms 93296 KB Output is correct
49 Correct 2 ms 256 KB Output is correct