oj.uz

Submission #276908

# Submission time Handle Problem Language Result Execution time Memory
276908 2020-08-20T18:37:29 Z _7_7_ Game (IOI13_game) C++14
80 / 100
 4516 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 = 660045, mod = 998244353, N = 9e6 + 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;

struct ST {
	int l, r;
	ll g;
};

ST T[N];

void upd1 (int pos, ll x, int v, int tl = 0, int tr = inf - 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 = inf - 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 = inf - 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 = inf - 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);
			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);
			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 = inf - 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 n, int m) {
	TT[++Sz1].v = ++Sz;
}

void update(int x, int y, ll z) {
//	cerr << x << ' ' << y << ' ' << z << endl;
	upd(x, y, z, 1);
}

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 376 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 2 ms 512 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 380 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 933 ms 29688 KB Output is correct
5 Correct 733 ms 30020 KB Output is correct
6 Correct 936 ms 26828 KB Output is correct
7 Correct 970 ms 26484 KB Output is correct
8 Correct 724 ms 17668 KB Output is correct
9 Correct 1004 ms 26668 KB Output is correct
10 Correct 958 ms 26548 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 2 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 1 ms 416 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 2 ms 512 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1415 ms 14056 KB Output is correct
13 Correct 1909 ms 7596 KB Output is correct
14 Correct 662 ms 3576 KB Output is correct
15 Correct 2252 ms 10152 KB Output is correct
16 Correct 642 ms 15068 KB Output is correct
17 Correct 1256 ms 11896 KB Output is correct
18 Correct 1974 ms 15608 KB Output is correct
19 Correct 1765 ms 15716 KB Output is correct
20 Correct 1853 ms 15024 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 384 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 2 ms 512 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 931 ms 29560 KB Output is correct
13 Correct 762 ms 30020 KB Output is correct
14 Correct 931 ms 26932 KB Output is correct
15 Correct 989 ms 26488 KB Output is correct
16 Correct 663 ms 17692 KB Output is correct
17 Correct 941 ms 26744 KB Output is correct
18 Correct 902 ms 26360 KB Output is correct
19 Correct 1404 ms 13932 KB Output is correct
20 Correct 1999 ms 7288 KB Output is correct
21 Correct 643 ms 3448 KB Output is correct
22 Correct 2148 ms 9512 KB Output is correct
23 Correct 639 ms 14712 KB Output is correct
24 Correct 1267 ms 11376 KB Output is correct
25 Correct 2116 ms 14716 KB Output is correct
26 Correct 1878 ms 15104 KB Output is correct
27 Correct 1793 ms 14352 KB Output is correct
28 Correct 817 ms 129024 KB Output is correct
29 Correct 1954 ms 141512 KB Output is correct
30 Correct 4296 ms 102736 KB Output is correct
31 Correct 4034 ms 78844 KB Output is correct
32 Correct 593 ms 1912 KB Output is correct
33 Correct 747 ms 3160 KB Output is correct
34 Correct 519 ms 138664 KB Output is correct
35 Correct 1305 ms 71288 KB Output is correct
36 Correct 2531 ms 138968 KB Output is correct
37 Correct 2161 ms 139248 KB Output is correct
38 Correct 2142 ms 138616 KB Output is correct
39 Correct 1696 ms 107212 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 2 ms 332 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 2 ms 640 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 923 ms 29628 KB Output is correct
13 Correct 721 ms 29816 KB Output is correct
14 Correct 936 ms 26940 KB Output is correct
15 Correct 1030 ms 26444 KB Output is correct
16 Correct 672 ms 17748 KB Output is correct
17 Correct 942 ms 26620 KB Output is correct
18 Correct 970 ms 26208 KB Output is correct
19 Correct 1432 ms 13608 KB Output is correct
20 Correct 1839 ms 7120 KB Output is correct
21 Correct 673 ms 3192 KB Output is correct
22 Correct 2251 ms 9312 KB Output is correct
23 Correct 652 ms 13996 KB Output is correct
24 Correct 1261 ms 10844 KB Output is correct
25 Correct 2005 ms 14324 KB Output is correct
26 Correct 1761 ms 14512 KB Output is correct
27 Correct 1822 ms 13568 KB Output is correct
28 Correct 861 ms 127204 KB Output is correct
29 Correct 1866 ms 141128 KB Output is correct
30 Correct 4516 ms 102288 KB Output is correct
31 Correct 4180 ms 78640 KB Output is correct
32 Correct 594 ms 1784 KB Output is correct
33 Correct 756 ms 3264 KB Output is correct
34 Correct 508 ms 138488 KB Output is correct
35 Correct 1676 ms 70904 KB Output is correct
36 Correct 2705 ms 138848 KB Output is correct
37 Correct 2140 ms 138976 KB Output is correct
38 Correct 2150 ms 138416 KB Output is correct
39 Runtime error 821 ms 256000 KB Execution killed with signal 11
40 Halted 0 ms 0 KB -