oj.uz

Submission #278377

# Submission time Handle Problem Language Result Execution time Memory
278377 2020-08-21T12:16:02 Z _7_7_ Game (IOI13_game) C++
80 / 100
 4242 ms 225656 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 = 3e5 + 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 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 0 ms 256 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 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 599 ms 8696 KB Output is correct
5 Correct 442 ms 8884 KB Output is correct
6 Correct 484 ms 5624 KB Output is correct
7 Correct 543 ms 5368 KB Output is correct
8 Correct 382 ms 4480 KB Output is correct
9 Correct 518 ms 5672 KB Output is correct
10 Correct 517 ms 5324 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 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 360 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 974 ms 10264 KB Output is correct
13 Correct 1465 ms 3660 KB Output is correct
14 Correct 317 ms 960 KB Output is correct
15 Correct 1786 ms 4924 KB Output is correct
16 Correct 223 ms 9724 KB Output is correct
17 Correct 785 ms 6648 KB Output is correct
18 Correct 1346 ms 10088 KB Output is correct
19 Correct 1169 ms 10232 KB Output is correct
20 Correct 1098 ms 9592 KB Output is correct
21 Correct 0 ms 384 KB Output is correct

Subtask #4
17.0 / 17.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 0 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 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 621 ms 8612 KB Output is correct
13 Correct 468 ms 8824 KB Output is correct
14 Correct 518 ms 5700 KB Output is correct
15 Correct 578 ms 5536 KB Output is correct
16 Correct 394 ms 4320 KB Output is correct
17 Correct 549 ms 5496 KB Output is correct
18 Correct 547 ms 5376 KB Output is correct
19 Correct 991 ms 10196 KB Output is correct
20 Correct 1521 ms 3632 KB Output is correct
21 Correct 328 ms 1144 KB Output is correct
22 Correct 1786 ms 4896 KB Output is correct
23 Correct 241 ms 9716 KB Output is correct
24 Correct 756 ms 6520 KB Output is correct
25 Correct 1268 ms 10232 KB Output is correct
26 Correct 1084 ms 10292 KB Output is correct
27 Correct 1024 ms 9656 KB Output is correct
28 Correct 815 ms 125944 KB Output is correct
29 Correct 2154 ms 140832 KB Output is correct
30 Correct 4027 ms 101892 KB Output is correct
31 Correct 3758 ms 77912 KB Output is correct
32 Correct 569 ms 1124 KB Output is correct
33 Correct 733 ms 2528 KB Output is correct
34 Correct 483 ms 137848 KB Output is correct
35 Correct 1374 ms 70384 KB Output is correct
36 Correct 2496 ms 138616 KB Output is correct
37 Correct 2211 ms 138252 KB Output is correct
38 Correct 1979 ms 137848 KB Output is correct
39 Correct 1843 ms 106360 KB Output is correct
40 Correct 1 ms 256 KB Output is correct

Subtask #5
0 / 20.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 0 ms 256 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 591 ms 8568 KB Output is correct
13 Correct 437 ms 8824 KB Output is correct
14 Correct 480 ms 5756 KB Output is correct
15 Correct 529 ms 5368 KB Output is correct
16 Correct 421 ms 4472 KB Output is correct
17 Correct 518 ms 5656 KB Output is correct
18 Correct 482 ms 5200 KB Output is correct
19 Correct 943 ms 10232 KB Output is correct
20 Correct 1465 ms 3960 KB Output is correct
21 Correct 307 ms 1016 KB Output is correct
22 Correct 1737 ms 5236 KB Output is correct
23 Correct 244 ms 9704 KB Output is correct
24 Correct 851 ms 6648 KB Output is correct
25 Correct 1672 ms 10128 KB Output is correct
26 Correct 1299 ms 10104 KB Output is correct
27 Correct 1233 ms 9580 KB Output is correct
28 Correct 969 ms 125560 KB Output is correct
29 Correct 1979 ms 140856 KB Output is correct
30 Correct 4242 ms 101800 KB Output is correct
31 Correct 3929 ms 78104 KB Output is correct
32 Correct 569 ms 1144 KB Output is correct
33 Correct 729 ms 2480 KB Output is correct
34 Correct 485 ms 137848 KB Output is correct
35 Correct 1297 ms 70416 KB Output is correct
36 Correct 2631 ms 138360 KB Output is correct
37 Correct 1978 ms 138360 KB Output is correct
38 Correct 2017 ms 137876 KB Output is correct
39 Incorrect 929 ms 225656 KB Output isn't correct
40 Halted 0 ms 0 KB -