oj.uz

Submission #134360

# Submission time Handle Problem Language Result Execution time Memory
134360 2019-07-22T13:44:21 Z ksmzzang2003 Game (IOI13_game) C++17
100 / 100
 8840 ms 173284 KB 
#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

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 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 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 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 834 ms 13748 KB Output is correct
5 Correct 607 ms 13620 KB Output is correct
6 Correct 730 ms 11044 KB Output is correct
7 Correct 858 ms 10748 KB Output is correct
8 Correct 545 ms 8608 KB Output is correct
9 Correct 840 ms 10780 KB Output is correct
10 Correct 919 ms 10616 KB Output is correct
11 Correct 3 ms 256 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 3 ms 380 KB Output is correct
3 Correct 3 ms 364 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 400 KB Output is correct
9 Correct 2 ms 360 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 1494 ms 17032 KB Output is correct
13 Correct 2852 ms 10888 KB Output is correct
14 Correct 439 ms 5752 KB Output is correct
15 Correct 3204 ms 13580 KB Output is correct
16 Correct 292 ms 15864 KB Output is correct
17 Correct 1303 ms 12028 KB Output is correct
18 Correct 2394 ms 17360 KB Output is correct
19 Correct 1919 ms 17476 KB Output is correct
20 Correct 1739 ms 16888 KB Output is correct
21 Correct 2 ms 504 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 2 ms 380 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 380 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 380 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 380 KB Output is correct
12 Correct 850 ms 13672 KB Output is correct
13 Correct 628 ms 13556 KB Output is correct
14 Correct 729 ms 11224 KB Output is correct
15 Correct 938 ms 11004 KB Output is correct
16 Correct 512 ms 8600 KB Output is correct
17 Correct 787 ms 10752 KB Output is correct
18 Correct 751 ms 10232 KB Output is correct
19 Correct 1453 ms 17168 KB Output is correct
20 Correct 2810 ms 10796 KB Output is correct
21 Correct 408 ms 5796 KB Output is correct
22 Correct 3245 ms 13528 KB Output is correct
23 Correct 286 ms 15864 KB Output is correct
24 Correct 1238 ms 12152 KB Output is correct
25 Correct 2433 ms 17600 KB Output is correct
26 Correct 1959 ms 17500 KB Output is correct
27 Correct 1789 ms 16916 KB Output is correct
28 Correct 801 ms 56016 KB Output is correct
29 Correct 2192 ms 51176 KB Output is correct
30 Correct 6846 ms 48188 KB Output is correct
31 Correct 6514 ms 87480 KB Output is correct
32 Correct 902 ms 10628 KB Output is correct
33 Correct 1222 ms 14572 KB Output is correct
34 Correct 412 ms 44792 KB Output is correct
35 Correct 1695 ms 29792 KB Output is correct
36 Correct 3188 ms 49052 KB Output is correct
37 Correct 2832 ms 49252 KB Output is correct
38 Correct 2345 ms 48600 KB Output is correct
39 Correct 2120 ms 40064 KB Output is correct
40 Correct 2 ms 376 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 3 ms 380 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 851 ms 13900 KB Output is correct
13 Correct 613 ms 13628 KB Output is correct
14 Correct 733 ms 11200 KB Output is correct
15 Correct 834 ms 10880 KB Output is correct
16 Correct 517 ms 8696 KB Output is correct
17 Correct 845 ms 10836 KB Output is correct
18 Correct 715 ms 10612 KB Output is correct
19 Correct 1452 ms 17028 KB Output is correct
20 Correct 2882 ms 10772 KB Output is correct
21 Correct 409 ms 5664 KB Output is correct
22 Correct 3224 ms 13628 KB Output is correct
23 Correct 289 ms 15964 KB Output is correct
24 Correct 1233 ms 12080 KB Output is correct
25 Correct 2192 ms 17348 KB Output is correct
26 Correct 1887 ms 17548 KB Output is correct
27 Correct 1785 ms 17104 KB Output is correct
28 Correct 840 ms 56084 KB Output is correct
29 Correct 2420 ms 51164 KB Output is correct
30 Correct 7209 ms 48240 KB Output is correct
31 Correct 6740 ms 87456 KB Output is correct
32 Correct 933 ms 10920 KB Output is correct
33 Correct 1259 ms 14436 KB Output is correct
34 Correct 400 ms 44868 KB Output is correct
35 Correct 1845 ms 29860 KB Output is correct
36 Correct 2970 ms 49132 KB Output is correct
37 Correct 2613 ms 49224 KB Output is correct
38 Correct 2592 ms 48780 KB Output is correct
39 Correct 1128 ms 111048 KB Output is correct
40 Correct 3303 ms 94960 KB Output is correct
41 Correct 8840 ms 95568 KB Output is correct
42 Correct 8669 ms 173284 KB Output is correct
43 Correct 802 ms 89356 KB Output is correct
44 Correct 1509 ms 11016 KB Output is correct
45 Correct 2078 ms 40012 KB Output is correct
46 Correct 4051 ms 93604 KB Output is correct
47 Correct 3893 ms 93764 KB Output is correct
48 Correct 4191 ms 93172 KB Output is correct
49 Correct 2 ms 376 KB Output is correct