oj.uz

Submission #278737

# Submission time Handle Problem Language Result Execution time Memory
278737 2020-08-21T17:35:28 Z _7_7_ Game (IOI13_game) C++14
100 / 100
 5774 ms 252856 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 = 1e7 + 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 130 ms 235128 KB Output is correct
2 Correct 132 ms 235128 KB Output is correct
3 Correct 132 ms 235128 KB Output is correct
4 Correct 130 ms 235264 KB Output is correct
5 Correct 130 ms 235132 KB Output is correct
6 Correct 130 ms 235128 KB Output is correct
7 Correct 132 ms 235256 KB Output is correct
8 Correct 132 ms 235128 KB Output is correct
9 Correct 129 ms 235128 KB Output is correct
10 Correct 131 ms 235204 KB Output is correct
11 Correct 131 ms 235128 KB Output is correct
12 Correct 130 ms 235128 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 235128 KB Output is correct
2 Correct 131 ms 235128 KB Output is correct
3 Correct 131 ms 235128 KB Output is correct
4 Correct 1114 ms 243704 KB Output is correct
5 Correct 957 ms 243448 KB Output is correct
6 Correct 1067 ms 240848 KB Output is correct
7 Correct 1199 ms 240672 KB Output is correct
8 Correct 820 ms 241016 KB Output is correct
9 Correct 1239 ms 240776 KB Output is correct
10 Correct 1214 ms 240352 KB Output is correct
11 Correct 130 ms 235128 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 235204 KB Output is correct
2 Correct 132 ms 235228 KB Output is correct
3 Correct 140 ms 235128 KB Output is correct
4 Correct 130 ms 235128 KB Output is correct
5 Correct 128 ms 235128 KB Output is correct
6 Correct 131 ms 235128 KB Output is correct
7 Correct 134 ms 235084 KB Output is correct
8 Correct 130 ms 235156 KB Output is correct
9 Correct 133 ms 235140 KB Output is correct
10 Correct 143 ms 235128 KB Output is correct
11 Correct 136 ms 235128 KB Output is correct
12 Correct 1961 ms 243320 KB Output is correct
13 Correct 2437 ms 240156 KB Output is correct
14 Correct 985 ms 240376 KB Output is correct
15 Correct 2791 ms 240316 KB Output is correct
16 Correct 952 ms 240276 KB Output is correct
17 Correct 1517 ms 241528 KB Output is correct
18 Correct 2751 ms 241512 KB Output is correct
19 Correct 2444 ms 241788 KB Output is correct
20 Correct 2184 ms 241260 KB Output is correct
21 Correct 132 ms 235128 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 235128 KB Output is correct
2 Correct 134 ms 235256 KB Output is correct
3 Correct 133 ms 235128 KB Output is correct
4 Correct 131 ms 235128 KB Output is correct
5 Correct 129 ms 235132 KB Output is correct
6 Correct 133 ms 235256 KB Output is correct
7 Correct 129 ms 235128 KB Output is correct
8 Correct 129 ms 235128 KB Output is correct
9 Correct 137 ms 235172 KB Output is correct
10 Correct 132 ms 235128 KB Output is correct
11 Correct 130 ms 235128 KB Output is correct
12 Correct 1109 ms 243832 KB Output is correct
13 Correct 949 ms 243524 KB Output is correct
14 Correct 1054 ms 240888 KB Output is correct
15 Correct 1131 ms 240632 KB Output is correct
16 Correct 816 ms 241144 KB Output is correct
17 Correct 1158 ms 240684 KB Output is correct
18 Correct 1127 ms 240376 KB Output is correct
19 Correct 1805 ms 243448 KB Output is correct
20 Correct 2303 ms 239992 KB Output is correct
21 Correct 967 ms 240504 KB Output is correct
22 Correct 2700 ms 240376 KB Output is correct
23 Correct 972 ms 240164 KB Output is correct
24 Correct 1642 ms 241400 KB Output is correct
25 Correct 2642 ms 241596 KB Output is correct
26 Correct 2231 ms 241684 KB Output is correct
27 Correct 2128 ms 241144 KB Output is correct
28 Correct 864 ms 243952 KB Output is correct
29 Correct 1649 ms 247420 KB Output is correct
30 Correct 4780 ms 243832 KB Output is correct
31 Correct 4612 ms 243704 KB Output is correct
32 Correct 921 ms 242760 KB Output is correct
33 Correct 1073 ms 242808 KB Output is correct
34 Correct 427 ms 244676 KB Output is correct
35 Correct 1066 ms 244208 KB Output is correct
36 Correct 2495 ms 244472 KB Output is correct
37 Correct 1840 ms 244840 KB Output is correct
38 Correct 1681 ms 244344 KB Output is correct
39 Correct 1422 ms 244472 KB Output is correct
40 Correct 126 ms 235128 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 235128 KB Output is correct
2 Correct 129 ms 235128 KB Output is correct
3 Correct 145 ms 235200 KB Output is correct
4 Correct 133 ms 235196 KB Output is correct
5 Correct 133 ms 235184 KB Output is correct
6 Correct 132 ms 235128 KB Output is correct
7 Correct 132 ms 235128 KB Output is correct
8 Correct 136 ms 235144 KB Output is correct
9 Correct 138 ms 235132 KB Output is correct
10 Correct 130 ms 235160 KB Output is correct
11 Correct 132 ms 235128 KB Output is correct
12 Correct 1192 ms 243620 KB Output is correct
13 Correct 1022 ms 243576 KB Output is correct
14 Correct 1117 ms 240892 KB Output is correct
15 Correct 1194 ms 240632 KB Output is correct
16 Correct 830 ms 241016 KB Output is correct
17 Correct 1225 ms 240736 KB Output is correct
18 Correct 1167 ms 240448 KB Output is correct
19 Correct 1873 ms 243380 KB Output is correct
20 Correct 2381 ms 239944 KB Output is correct
21 Correct 985 ms 240436 KB Output is correct
22 Correct 2780 ms 240376 KB Output is correct
23 Correct 959 ms 240248 KB Output is correct
24 Correct 1580 ms 241400 KB Output is correct
25 Correct 2746 ms 241724 KB Output is correct
26 Correct 2537 ms 241856 KB Output is correct
27 Correct 2223 ms 241204 KB Output is correct
28 Correct 911 ms 244916 KB Output is correct
29 Correct 1588 ms 249512 KB Output is correct
30 Correct 4704 ms 244048 KB Output is correct
31 Correct 4496 ms 243888 KB Output is correct
32 Correct 936 ms 243696 KB Output is correct
33 Correct 1102 ms 243868 KB Output is correct
34 Correct 411 ms 244856 KB Output is correct
35 Correct 1088 ms 245172 KB Output is correct
36 Correct 2242 ms 247752 KB Output is correct
37 Correct 1627 ms 247788 KB Output is correct
38 Correct 1661 ms 247140 KB Output is correct
39 Correct 1150 ms 250644 KB Output is correct
40 Correct 2460 ms 252856 KB Output is correct
41 Correct 5774 ms 245648 KB Output is correct
42 Correct 5488 ms 245204 KB Output is correct
43 Correct 639 ms 247620 KB Output is correct
44 Correct 1310 ms 245372 KB Output is correct
45 Correct 1426 ms 248568 KB Output is correct
46 Correct 2609 ms 251564 KB Output is correct
47 Correct 2736 ms 251488 KB Output is correct
48 Correct 2646 ms 251120 KB Output is correct
49 Correct 122 ms 235128 KB Output is correct