oj.uz

Submission #278740

# Submission time Handle Problem Language Result Execution time Memory
278740 2020-08-21T17:36:29 Z _7_7_ Game (IOI13_game) C++14
100 / 100
 5670 ms 127128 KB 
#include "game.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
//#define int long long
//#pragma GCC optimize("Ofast")
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
 
 
#define file(s) freopen(s".in","r",stdin); freopen(s".out","w",stdout);
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define all(x) x.begin(), x.end()
#define sz(s) (int)s.size()
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define s second
#define f first
 
 
 
 
typedef pair < long long, long long > pll;    
typedef unsigned long long ull;
typedef pair < int, int > pii;
typedef vector < pii > vpii;
typedef vector < int > vi;
typedef long double ldb;  
typedef long long ll;  
typedef double db;
 
typedef tree < int, null_type, less < int >, rb_tree_tag, tree_order_statistics_node_update > ordered_set;
 
const int inf = 1e9, maxn = 4e5 + 11, mod = 998244353, N = 5e6 + 11;
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1}, block = 300;
const pii base = mp(1171, 3307), Mod = mp(1e9 + 7, 1e9 + 9);
const db eps = 1e-12, pi = acos(-1);
const ll INF = 1e18;
 
int Sz, n, m;
int l, r, x, y;
ll z;
               	
ll gcd (ll x, ll y) {
	while (1) {
		if (x > y)
			swap(x, y);
		if (!x)				
			return y;		
//		cerr << x << ' ' << y << endl;
		y %= x;
	}
}
 
struct ST {
	int l, r, pos;
	ll g;
};
 
ST T[N];
 
void upd1 (int pos, ll x, int v, int tl = 0, int tr = m - 1) {
//	cerr << v << ' ' << tl << ' ' << tr << ' ' << pos << ' ' << x << endl;
	if (tl == tr) {
		T[v].g = x;
		return;
	}

	if (!T[v].l && !T[v].r && T[v].pos == -1) {
		T[v].pos = pos;
		T[v].g = x;
		return;
	}

	if (T[v].pos != -1) {
		if (T[v].pos == pos) {
			T[v].g = x;
			return;
		}
   		
		int u = T[v].pos;
		T[v].pos = -1;

		T[v].l = ++Sz;
		
		T[v].r = ++Sz;

		upd1(u, T[v].g, v, tl, tr);
	}
 
	int tm = (tl + tr) >> 1;
	if (pos <= tm) {
		if (!T[v].l) 
			T[v].l = ++Sz;
		upd1(pos, x, T[v].l, tl, tm);
	} else {
		if (!T[v].r)
			T[v].r = ++Sz;
		upd1(pos, x, T[v].r, tm + 1, tr);
	}
 
	T[v].g = gcd(T[T[v].l].g, T[T[v].r].g);
}
 
ll get1 (int l, int r, int v, int tl = 0, int tr = m - 1) {
	if (l > r || tl > r || l > tr)
		return 0;
 
    if (T[v].pos != -1) {
    	if (l <= T[v].pos && T[v].pos <= r)
    		return T[v].g;
		return 0;
    }

	if (l <= tl && tr <= r)
		return T[v].g;
 
	int tm = (tl + tr) >> 1;
	
	ll res = 0;
	
	if (T[v].l)
		res = get1(l, r, T[v].l, tl, tm);
 
	if (T[v].r)
		res = gcd(res, get1(l, r, T[v].r, tm + 1, tr));
 
 	return res;
}

struct STT {
	int l, r, v;
};
 
STT TT[maxn];
 
int Sz1;
 
 
 
void upd (int v = 1, int tl = 0, int tr = n - 1) {
//	cerr << tl << ' ' << tr << endl;
	if (tl == tr) {
		upd1(y, z, TT[v].v);
		return;
	}

	int tm = (tl + tr) >> 1;
 
	if (x <= tm) {
		if (!TT[v].l) {
//			assert(Sz + 1 < N);
//			assert(Sz1 + 1 < maxn);
//			if (Sz + 1 == N || Sz1 + 1 == maxn) 
//				exit(0);
			TT[v].l = ++Sz1;
			TT[Sz1].v = ++Sz;
		}
		upd(TT[v].l, tl, tm);
	} else {
		if (!TT[v].r) {
//			assert(Sz + 1 < N);
//			assert(Sz1 + 1 < maxn);
//			if (Sz + 1 == N || Sz1 + 1 == maxn) 
//				exit(0);			
			TT[v].r = ++Sz1;
			TT[Sz1].v = ++Sz;
		}
		upd(TT[v].r, tm + 1, tr);
	}
 
	ll cur = 0;
	if (TT[v].l) 
		cur = get1(y, y, TT[TT[v].l].v); 
	
	if (TT[v].r)
		cur = gcd(cur, get1(y, y, TT[TT[v].r].v));
 
	upd1(y, cur, TT[v].v);
//	cerr << tl << ' ' << tr << ' ' << cur << endl;
}
 
ll get (int v, int tl = 0, int tr = n - 1) {
	if (l > r || tl > r || l > tr)
		return 0;
 
	if (l <= tl && tr <= r) {
		return get1(x, y, TT[v].v); 
	}
 
	int tm = (tl + tr) >> 1;	
	
	ll res = 0;
	
	if (TT[v].l)
		res = get(TT[v].l, tl, tm);
 
	if (TT[v].r)
		res = gcd(res, get(TT[v].r, tm + 1, tr));
 
	return res;
}
 
 
void init(int r, int c) {
	for (int i = 0; i < N; ++i) {
		T[i].pos = -1; 
		T[i].g = 0;
	}

//	assert(0);
	n = r, m = c;
	n = inf, m = inf;
	TT[++Sz1].v = ++Sz;
}
 
void update(int X, int Y, ll Z) {
//	cerr << x << ' ' << y << ' ' << z << endl;
	x = X, y = Y, z = Z;
	upd(1);
//	cerr << Sz << ' ' << Sz1 << endl;
}
 
long long calculate(int L, int X, int R, int Y) {		
//	cerr << x << ' ' << y << ' ' << lf << ' ' << rg << endl;
	l = L, r = R, x = X, y = Y;
    return get(1);
}

Compilation message

grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
   18 |  int res;
      |      ^~~
game.cpp: In function 'll get1(int, int, int, int, int)':
game.cpp:115:6: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  115 |      if (l <= T[v].pos && T[v].pos <= r)
      |      ^~
game.cpp:117:3: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  117 |   return 0;
      |   ^~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 117712 KB Output is correct
2 Correct 62 ms 117796 KB Output is correct
3 Correct 65 ms 117752 KB Output is correct
4 Correct 60 ms 117752 KB Output is correct
5 Correct 59 ms 117752 KB Output is correct
6 Correct 68 ms 117752 KB Output is correct
7 Correct 59 ms 117756 KB Output is correct
8 Correct 65 ms 117752 KB Output is correct
9 Correct 76 ms 117752 KB Output is correct
10 Correct 70 ms 117752 KB Output is correct
11 Correct 70 ms 117884 KB Output is correct
12 Correct 59 ms 117752 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 117752 KB Output is correct
2 Correct 60 ms 117752 KB Output is correct
3 Correct 66 ms 117752 KB Output is correct
4 Correct 1090 ms 122852 KB Output is correct
5 Correct 894 ms 123160 KB Output is correct
6 Correct 1034 ms 119676 KB Output is correct
7 Correct 1186 ms 119264 KB Output is correct
8 Correct 767 ms 120440 KB Output is correct
9 Correct 1126 ms 119672 KB Output is correct
10 Correct 1062 ms 119032 KB Output is correct
11 Correct 65 ms 117752 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 117752 KB Output is correct
2 Correct 70 ms 117752 KB Output is correct
3 Correct 71 ms 117752 KB Output is correct
4 Correct 68 ms 117752 KB Output is correct
5 Correct 67 ms 117752 KB Output is correct
6 Correct 68 ms 117752 KB Output is correct
7 Correct 64 ms 117752 KB Output is correct
8 Correct 64 ms 117752 KB Output is correct
9 Correct 66 ms 117720 KB Output is correct
10 Correct 67 ms 117880 KB Output is correct
11 Correct 68 ms 117752 KB Output is correct
12 Correct 1797 ms 123176 KB Output is correct
13 Correct 2254 ms 119680 KB Output is correct
14 Correct 913 ms 119160 KB Output is correct
15 Correct 2741 ms 119392 KB Output is correct
16 Correct 934 ms 119592 KB Output is correct
17 Correct 1662 ms 119804 KB Output is correct
18 Correct 2867 ms 119104 KB Output is correct
19 Correct 2275 ms 119164 KB Output is correct
20 Correct 2084 ms 118572 KB Output is correct
21 Correct 71 ms 117752 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 117752 KB Output is correct
2 Correct 71 ms 117752 KB Output is correct
3 Correct 71 ms 117752 KB Output is correct
4 Correct 69 ms 117752 KB Output is correct
5 Correct 71 ms 117752 KB Output is correct
6 Correct 73 ms 117880 KB Output is correct
7 Correct 68 ms 117752 KB Output is correct
8 Correct 67 ms 117752 KB Output is correct
9 Correct 73 ms 117756 KB Output is correct
10 Correct 70 ms 117700 KB Output is correct
11 Correct 61 ms 117708 KB Output is correct
12 Correct 1131 ms 121812 KB Output is correct
13 Correct 1010 ms 122172 KB Output is correct
14 Correct 1044 ms 118900 KB Output is correct
15 Correct 1147 ms 118552 KB Output is correct
16 Correct 784 ms 119400 KB Output is correct
17 Correct 1155 ms 118728 KB Output is correct
18 Correct 1087 ms 118456 KB Output is correct
19 Correct 1761 ms 121984 KB Output is correct
20 Correct 2343 ms 118492 KB Output is correct
21 Correct 1014 ms 118392 KB Output is correct
22 Correct 2686 ms 118600 KB Output is correct
23 Correct 939 ms 118612 KB Output is correct
24 Correct 1577 ms 119252 KB Output is correct
25 Correct 2745 ms 118892 KB Output is correct
26 Correct 2642 ms 119012 KB Output is correct
27 Correct 2226 ms 118364 KB Output is correct
28 Correct 793 ms 120388 KB Output is correct
29 Correct 1496 ms 127128 KB Output is correct
30 Correct 4609 ms 121148 KB Output is correct
31 Correct 4453 ms 121184 KB Output is correct
32 Correct 845 ms 122132 KB Output is correct
33 Correct 1022 ms 122124 KB Output is correct
34 Correct 336 ms 122232 KB Output is correct
35 Correct 1080 ms 124092 KB Output is correct
36 Correct 1991 ms 124740 KB Output is correct
37 Correct 1593 ms 124944 KB Output is correct
38 Correct 1694 ms 124328 KB Output is correct
39 Correct 1379 ms 124444 KB Output is correct
40 Correct 62 ms 117752 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 117760 KB Output is correct
2 Correct 80 ms 117748 KB Output is correct
3 Correct 68 ms 117752 KB Output is correct
4 Correct 59 ms 117748 KB Output is correct
5 Correct 59 ms 117752 KB Output is correct
6 Correct 66 ms 117752 KB Output is correct
7 Correct 58 ms 117752 KB Output is correct
8 Correct 60 ms 117880 KB Output is correct
9 Correct 80 ms 117752 KB Output is correct
10 Correct 59 ms 117752 KB Output is correct
11 Correct 80 ms 117752 KB Output is correct
12 Correct 1085 ms 123764 KB Output is correct
13 Correct 883 ms 124024 KB Output is correct
14 Correct 1022 ms 120680 KB Output is correct
15 Correct 1080 ms 120500 KB Output is correct
16 Correct 719 ms 121344 KB Output is correct
17 Correct 1061 ms 120564 KB Output is correct
18 Correct 1059 ms 120148 KB Output is correct
19 Correct 1755 ms 123912 KB Output is correct
20 Correct 2239 ms 120400 KB Output is correct
21 Correct 900 ms 120208 KB Output is correct
22 Correct 2655 ms 120360 KB Output is correct
23 Correct 913 ms 120440 KB Output is correct
24 Correct 1448 ms 120956 KB Output is correct
25 Correct 2504 ms 120552 KB Output is correct
26 Correct 2352 ms 120800 KB Output is correct
27 Correct 2077 ms 120056 KB Output is correct
28 Correct 697 ms 124280 KB Output is correct
29 Correct 1447 ms 123644 KB Output is correct
30 Correct 4583 ms 119652 KB Output is correct
31 Correct 4326 ms 119452 KB Output is correct
32 Correct 890 ms 118264 KB Output is correct
33 Correct 998 ms 118472 KB Output is correct
34 Correct 341 ms 120568 KB Output is correct
35 Correct 1052 ms 120268 KB Output is correct
36 Correct 1966 ms 121156 KB Output is correct
37 Correct 1445 ms 121256 KB Output is correct
38 Correct 1378 ms 120440 KB Output is correct
39 Correct 916 ms 122592 KB Output is correct
40 Correct 2255 ms 124988 KB Output is correct
41 Correct 5670 ms 120768 KB Output is correct
42 Correct 5394 ms 120312 KB Output is correct
43 Correct 543 ms 122736 KB Output is correct
44 Correct 1219 ms 118432 KB Output is correct
45 Correct 1250 ms 120824 KB Output is correct
46 Correct 2347 ms 123268 KB Output is correct
47 Correct 2344 ms 123092 KB Output is correct
48 Correct 2479 ms 123044 KB Output is correct
49 Correct 65 ms 117756 KB Output is correct