oj.uz

Submission #276914

# Submission time Handle Problem Language Result Execution time Memory
276914 2020-08-20T18:46:23 Z _7_7_ Game (IOI13_game) C++14
80 / 100
 4302 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 = 660045, mod = 998244353, N = 2e7 + 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) {
//	assert(0);
	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 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 384 KB Output is correct
5 Correct 1 ms 256 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 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 1030 ms 27976 KB Output is correct
5 Correct 762 ms 28152 KB Output is correct
6 Correct 1018 ms 25088 KB Output is correct
7 Correct 1022 ms 24884 KB Output is correct
8 Correct 686 ms 15976 KB Output is correct
9 Correct 1004 ms 24952 KB Output is correct
10 Correct 966 ms 24632 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 3 ms 512 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 256 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 1481 ms 11972 KB Output is correct
13 Correct 1937 ms 5404 KB Output is correct
14 Correct 634 ms 1588 KB Output is correct
15 Correct 2162 ms 7836 KB Output is correct
16 Correct 662 ms 12768 KB Output is correct
17 Correct 1280 ms 9764 KB Output is correct
18 Correct 2285 ms 13240 KB Output is correct
19 Correct 1968 ms 13176 KB Output is correct
20 Correct 1852 ms 12720 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 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 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 2 ms 384 KB Output is correct
12 Correct 956 ms 28264 KB Output is correct
13 Correct 742 ms 28168 KB Output is correct
14 Correct 976 ms 25080 KB Output is correct
15 Correct 978 ms 24900 KB Output is correct
16 Correct 688 ms 16120 KB Output is correct
17 Correct 987 ms 25080 KB Output is correct
18 Correct 920 ms 24508 KB Output is correct
19 Correct 1403 ms 12280 KB Output is correct
20 Correct 1893 ms 5544 KB Output is correct
21 Correct 631 ms 1528 KB Output is correct
22 Correct 2189 ms 8108 KB Output is correct
23 Correct 698 ms 13056 KB Output is correct
24 Correct 1455 ms 9592 KB Output is correct
25 Correct 2401 ms 13140 KB Output is correct
26 Correct 2108 ms 13284 KB Output is correct
27 Correct 1843 ms 12696 KB Output is correct
28 Correct 1004 ms 126456 KB Output is correct
29 Correct 1951 ms 141688 KB Output is correct
30 Correct 4302 ms 103232 KB Output is correct
31 Correct 4202 ms 79224 KB Output is correct
32 Correct 590 ms 2424 KB Output is correct
33 Correct 755 ms 3704 KB Output is correct
34 Correct 516 ms 139128 KB Output is correct
35 Correct 1443 ms 71772 KB Output is correct
36 Correct 2398 ms 139364 KB Output is correct
37 Correct 1991 ms 139384 KB Output is correct
38 Correct 2081 ms 138196 KB Output is correct
39 Correct 1799 ms 106872 KB Output is correct
40 Correct 1 ms 376 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 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 256 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 990 ms 28324 KB Output is correct
13 Correct 729 ms 28408 KB Output is correct
14 Correct 923 ms 25616 KB Output is correct
15 Correct 984 ms 25464 KB Output is correct
16 Correct 692 ms 16604 KB Output is correct
17 Correct 978 ms 25464 KB Output is correct
18 Correct 903 ms 25080 KB Output is correct
19 Correct 1380 ms 12720 KB Output is correct
20 Correct 1832 ms 6224 KB Output is correct
21 Correct 650 ms 1940 KB Output is correct
22 Correct 2165 ms 8408 KB Output is correct
23 Correct 700 ms 13236 KB Output is correct
24 Correct 1277 ms 9980 KB Output is correct
25 Correct 2082 ms 13692 KB Output is correct
26 Correct 1810 ms 13784 KB Output is correct
27 Correct 1721 ms 13176 KB Output is correct
28 Correct 840 ms 127096 KB Output is correct
29 Correct 1913 ms 141644 KB Output is correct
30 Correct 4271 ms 102544 KB Output is correct
31 Correct 4057 ms 78796 KB Output is correct
32 Correct 586 ms 1848 KB Output is correct
33 Correct 767 ms 3160 KB Output is correct
34 Correct 492 ms 138616 KB Output is correct
35 Correct 1313 ms 71332 KB Output is correct
36 Correct 2456 ms 139332 KB Output is correct
37 Correct 2199 ms 139360 KB Output is correct
38 Correct 1930 ms 138528 KB Output is correct
39 Runtime error 1141 ms 256004 KB Execution killed with signal 9
40 Halted 0 ms 0 KB -