oj.uz

Submission #278578

# Submission time Handle Problem Language Result Execution time Memory
278578 2020-08-21T14:51:53 Z _7_7_ Game (IOI13_game) C++14
80 / 100
 4148 ms 256004 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 + 7e6 + 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;
	ll g;
};
 
ST T[N];
 
void upd1 (int pos, ll x, int v, int tl = 0, int tr = m - 1) {
	if (tl == tr) {
		T[v].g = x;
		return;
	}
 
	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 (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;
}
 
ll get2 (int pos, int v, int tl = 0, int tr = m - 1) {
	if (tl == tr) 
		return T[v].g; 
 
	int tm = (tl + tr) >> 1;
	if (pos <= tm) {
		if (!T[v].l)
			return 0;
		return get2(pos, T[v].l, tl, tm);
	}
 
	if (!T[v].r)
		return 0;
 
	return get2(pos, T[v].r, tm + 1, tr);
}
 
 
struct STT {
	int l, r, v;
};
 
STT TT[maxn];
 
int Sz1;
 
 
 
void upd (int v = 1, int tl = 0, int tr = n - 1) {
	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 = get2(y, TT[TT[v].l].v); 
	
	if (TT[v].r)
		cur = gcd(cur, get2(y, TT[TT[v].r].v));
 
	upd1(y, cur, TT[v].v);
}
 
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) {
//	assert(0);
	n = r, m = c;
	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;
      |      ^~~

Subtask #1
10.0 / 10.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 579 ms 9716 KB Output is correct
5 Correct 470 ms 10052 KB Output is correct
6 Correct 503 ms 6856 KB Output is correct
7 Correct 516 ms 6576 KB Output is correct
8 Correct 372 ms 5440 KB Output is correct
9 Correct 544 ms 6576 KB Output is correct
10 Correct 461 ms 6152 KB Output is correct
11 Correct 1 ms 384 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 928 ms 11392 KB Output is correct
13 Correct 1456 ms 4888 KB Output is correct
14 Correct 306 ms 2168 KB Output is correct
15 Correct 1751 ms 6116 KB Output is correct
16 Correct 238 ms 10744 KB Output is correct
17 Correct 824 ms 7672 KB Output is correct
18 Correct 1246 ms 11132 KB Output is correct
19 Correct 1082 ms 11256 KB Output is correct
20 Correct 994 ms 10616 KB Output is correct
21 Correct 1 ms 384 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 416 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 576 ms 9720 KB Output is correct
13 Correct 450 ms 10104 KB Output is correct
14 Correct 487 ms 6904 KB Output is correct
15 Correct 560 ms 6520 KB Output is correct
16 Correct 373 ms 5496 KB Output is correct
17 Correct 535 ms 6660 KB Output is correct
18 Correct 471 ms 6136 KB Output is correct
19 Correct 997 ms 11384 KB Output is correct
20 Correct 1467 ms 4988 KB Output is correct
21 Correct 304 ms 2044 KB Output is correct
22 Correct 1732 ms 6268 KB Output is correct
23 Correct 222 ms 10744 KB Output is correct
24 Correct 787 ms 7672 KB Output is correct
25 Correct 1399 ms 11128 KB Output is correct
26 Correct 1090 ms 11320 KB Output is correct
27 Correct 987 ms 10652 KB Output is correct
28 Correct 765 ms 126712 KB Output is correct
29 Correct 1895 ms 141908 KB Output is correct
30 Correct 4148 ms 102916 KB Output is correct
31 Correct 3725 ms 79120 KB Output is correct
32 Correct 553 ms 2296 KB Output is correct
33 Correct 724 ms 3576 KB Output is correct
34 Correct 501 ms 139000 KB Output is correct
35 Correct 1276 ms 71372 KB Output is correct
36 Correct 2616 ms 139260 KB Output is correct
37 Correct 2291 ms 139956 KB Output is correct
38 Correct 1951 ms 139480 KB Output is correct
39 Correct 1647 ms 107928 KB Output is correct
40 Correct 1 ms 384 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 606 ms 10360 KB Output is correct
13 Correct 448 ms 10516 KB Output is correct
14 Correct 512 ms 7352 KB Output is correct
15 Correct 554 ms 7000 KB Output is correct
16 Correct 381 ms 6008 KB Output is correct
17 Correct 509 ms 7160 KB Output is correct
18 Correct 472 ms 6648 KB Output is correct
19 Correct 958 ms 11768 KB Output is correct
20 Correct 1442 ms 5368 KB Output is correct
21 Correct 315 ms 2552 KB Output is correct
22 Correct 1751 ms 6560 KB Output is correct
23 Correct 221 ms 11240 KB Output is correct
24 Correct 750 ms 8312 KB Output is correct
25 Correct 1238 ms 11336 KB Output is correct
26 Correct 1168 ms 11436 KB Output is correct
27 Correct 1108 ms 10744 KB Output is correct
28 Correct 799 ms 127608 KB Output is correct
29 Correct 1887 ms 142212 KB Output is correct
30 Correct 4030 ms 102708 KB Output is correct
31 Correct 3696 ms 78912 KB Output is correct
32 Correct 553 ms 1912 KB Output is correct
33 Correct 730 ms 3244 KB Output is correct
34 Correct 482 ms 138544 KB Output is correct
35 Correct 1300 ms 71284 KB Output is correct
36 Correct 2555 ms 139912 KB Output is correct
37 Correct 2043 ms 139896 KB Output is correct
38 Correct 1934 ms 139128 KB Output is correct
39 Runtime error 1114 ms 256004 KB Execution killed with signal 9
40 Halted 0 ms 0 KB -