oj.uz

Submission #278278

# Submission time Handle Problem Language Result Execution time Memory
278278 2020-08-21T11:36:01 Z _7_7_ Game (IOI13_game) C++14
80 / 100
 4466 ms 256000 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 = 5e5 + 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;

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 x, int y, ll z, 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(x, y, z, 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(x, y, z, 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 l, int r, int x, int y, 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(l, r, x, y, TT[v].l, tl, tm);

	if (TT[v].r)
		res = __gcd(res, get(l, r, x, y, 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;
	upd(x, y, z, 1);
//	cerr << Sz << ' ' << Sz1 << endl;
}

long long calculate(int lf, int x, int rg, int y) {		
//	cerr << x << ' ' << y << ' ' << lf << ' ' << rg << endl;
    return get(lf, rg, x, y, 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 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 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 689 ms 9816 KB Output is correct
5 Correct 604 ms 10108 KB Output is correct
6 Correct 594 ms 6904 KB Output is correct
7 Correct 670 ms 6648 KB Output is correct
8 Correct 420 ms 5592 KB Output is correct
9 Correct 507 ms 6776 KB Output is correct
10 Correct 514 ms 6496 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 0 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 997 ms 11488 KB Output is correct
13 Correct 1613 ms 4820 KB Output is correct
14 Correct 318 ms 2164 KB Output is correct
15 Correct 1830 ms 6272 KB Output is correct
16 Correct 214 ms 11000 KB Output is correct
17 Correct 807 ms 7928 KB Output is correct
18 Correct 1477 ms 11180 KB Output is correct
19 Correct 1148 ms 11420 KB Output is correct
20 Correct 1120 ms 10684 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 308 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 599 ms 9936 KB Output is correct
13 Correct 479 ms 10184 KB Output is correct
14 Correct 572 ms 6904 KB Output is correct
15 Correct 607 ms 6648 KB Output is correct
16 Correct 370 ms 5640 KB Output is correct
17 Correct 513 ms 6744 KB Output is correct
18 Correct 465 ms 6564 KB Output is correct
19 Correct 996 ms 11440 KB Output is correct
20 Correct 1539 ms 4856 KB Output is correct
21 Correct 317 ms 2168 KB Output is correct
22 Correct 1808 ms 6392 KB Output is correct
23 Correct 221 ms 10872 KB Output is correct
24 Correct 758 ms 7928 KB Output is correct
25 Correct 1504 ms 11384 KB Output is correct
26 Correct 1290 ms 11512 KB Output is correct
27 Correct 1146 ms 10744 KB Output is correct
28 Correct 901 ms 128376 KB Output is correct
29 Correct 1912 ms 143544 KB Output is correct
30 Correct 4434 ms 104488 KB Output is correct
31 Correct 4274 ms 80536 KB Output is correct
32 Correct 589 ms 3708 KB Output is correct
33 Correct 797 ms 4984 KB Output is correct
34 Correct 506 ms 140408 KB Output is correct
35 Correct 1403 ms 72824 KB Output is correct
36 Correct 2571 ms 140220 KB Output is correct
37 Correct 2342 ms 140108 KB Output is correct
38 Correct 2245 ms 139404 KB Output is correct
39 Correct 1879 ms 108052 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 416 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 645 ms 9720 KB Output is correct
13 Correct 449 ms 9720 KB Output is correct
14 Correct 469 ms 6908 KB Output is correct
15 Correct 543 ms 6648 KB Output is correct
16 Correct 394 ms 5240 KB Output is correct
17 Correct 565 ms 7032 KB Output is correct
18 Correct 583 ms 6520 KB Output is correct
19 Correct 984 ms 11068 KB Output is correct
20 Correct 1537 ms 4672 KB Output is correct
21 Correct 319 ms 2220 KB Output is correct
22 Correct 1871 ms 6200 KB Output is correct
23 Correct 213 ms 10488 KB Output is correct
24 Correct 753 ms 8332 KB Output is correct
25 Correct 1469 ms 11980 KB Output is correct
26 Correct 1220 ms 12024 KB Output is correct
27 Correct 992 ms 11452 KB Output is correct
28 Correct 963 ms 127316 KB Output is correct
29 Correct 2041 ms 142512 KB Output is correct
30 Correct 4466 ms 103736 KB Output is correct
31 Correct 4091 ms 79956 KB Output is correct
32 Correct 619 ms 2868 KB Output is correct
33 Correct 808 ms 4088 KB Output is correct
34 Correct 509 ms 139512 KB Output is correct
35 Correct 1338 ms 72184 KB Output is correct
36 Correct 2383 ms 140156 KB Output is correct
37 Correct 2092 ms 139844 KB Output is correct
38 Correct 2159 ms 138472 KB Output is correct
39 Runtime error 1207 ms 256000 KB Execution killed with signal 9
40 Halted 0 ms 0 KB -