oj.uz

Submission #278385

# Submission time Handle Problem Language Result Execution time Memory
278385 2020-08-21T12:18:41 Z _7_7_ Game (IOI13_game) C++
80 / 100
 4161 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 = 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;
               	
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 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 256 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 0 ms 384 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 583 ms 8568 KB Output is correct
5 Correct 441 ms 8904 KB Output is correct
6 Correct 480 ms 5624 KB Output is correct
7 Correct 519 ms 5496 KB Output is correct
8 Correct 368 ms 4344 KB Output is correct
9 Correct 535 ms 5668 KB Output is correct
10 Correct 458 ms 5112 KB Output is correct
11 Correct 0 ms 256 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 0 ms 256 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 0 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 1047 ms 10188 KB Output is correct
13 Correct 1557 ms 3572 KB Output is correct
14 Correct 384 ms 1120 KB Output is correct
15 Correct 1802 ms 5272 KB Output is correct
16 Correct 245 ms 9752 KB Output is correct
17 Correct 777 ms 6648 KB Output is correct
18 Correct 1341 ms 10104 KB Output is correct
19 Correct 1167 ms 10188 KB Output is correct
20 Correct 1096 ms 9720 KB Output is correct
21 Correct 1 ms 256 KB Output is correct

Subtask #4
17.0 / 17.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 256 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 0 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 587 ms 8688 KB Output is correct
13 Correct 442 ms 8868 KB Output is correct
14 Correct 473 ms 5752 KB Output is correct
15 Correct 505 ms 5496 KB Output is correct
16 Correct 371 ms 4344 KB Output is correct
17 Correct 504 ms 5516 KB Output is correct
18 Correct 467 ms 5112 KB Output is correct
19 Correct 943 ms 10168 KB Output is correct
20 Correct 1497 ms 3648 KB Output is correct
21 Correct 311 ms 1016 KB Output is correct
22 Correct 1827 ms 5220 KB Output is correct
23 Correct 225 ms 9720 KB Output is correct
24 Correct 811 ms 6672 KB Output is correct
25 Correct 1339 ms 10232 KB Output is correct
26 Correct 1127 ms 10316 KB Output is correct
27 Correct 1050 ms 9760 KB Output is correct
28 Correct 794 ms 125688 KB Output is correct
29 Correct 1861 ms 140908 KB Output is correct
30 Correct 4161 ms 102072 KB Output is correct
31 Correct 3754 ms 78140 KB Output is correct
32 Correct 571 ms 1096 KB Output is correct
33 Correct 738 ms 2424 KB Output is correct
34 Correct 533 ms 137772 KB Output is correct
35 Correct 1452 ms 70264 KB Output is correct
36 Correct 2444 ms 138500 KB Output is correct
37 Correct 2049 ms 138484 KB Output is correct
38 Correct 1956 ms 137864 KB Output is correct
39 Correct 1693 ms 106504 KB Output is correct
40 Correct 0 ms 384 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 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 586 ms 8568 KB Output is correct
13 Correct 436 ms 8876 KB Output is correct
14 Correct 472 ms 5752 KB Output is correct
15 Correct 524 ms 5528 KB Output is correct
16 Correct 382 ms 4340 KB Output is correct
17 Correct 532 ms 5496 KB Output is correct
18 Correct 512 ms 5240 KB Output is correct
19 Correct 957 ms 10104 KB Output is correct
20 Correct 1483 ms 3704 KB Output is correct
21 Correct 315 ms 888 KB Output is correct
22 Correct 1743 ms 5096 KB Output is correct
23 Correct 218 ms 9720 KB Output is correct
24 Correct 763 ms 6520 KB Output is correct
25 Correct 1370 ms 10096 KB Output is correct
26 Correct 1212 ms 10324 KB Output is correct
27 Correct 1162 ms 9768 KB Output is correct
28 Correct 812 ms 125820 KB Output is correct
29 Correct 1938 ms 140664 KB Output is correct
30 Correct 3928 ms 101824 KB Output is correct
31 Correct 3832 ms 78328 KB Output is correct
32 Correct 587 ms 1096 KB Output is correct
33 Correct 736 ms 2296 KB Output is correct
34 Correct 488 ms 137848 KB Output is correct
35 Correct 1289 ms 70264 KB Output is correct
36 Correct 2514 ms 138144 KB Output is correct
37 Correct 2422 ms 138344 KB Output is correct
38 Correct 2133 ms 137752 KB Output is correct
39 Runtime error 1219 ms 256000 KB Execution killed with signal 9
40 Halted 0 ms 0 KB -