oj.uz

Submission #276920

# Submission time Handle Problem Language Result Execution time Memory
276920 2020-08-20T18:57:14 Z _7_7_ Game (IOI13_game) C++14
80 / 100
 4579 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 = 4e6 + 11, mod = 998244353, N = 1e7 + 8e6 + 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 964 ms 27400 KB Output is correct
5 Correct 760 ms 27620 KB Output is correct
6 Correct 1051 ms 24568 KB Output is correct
7 Correct 1056 ms 24244 KB Output is correct
8 Correct 703 ms 15352 KB Output is correct
9 Correct 1010 ms 24544 KB Output is correct
10 Correct 952 ms 23984 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 2 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1425 ms 11768 KB Output is correct
13 Correct 1861 ms 5056 KB Output is correct
14 Correct 647 ms 1228 KB Output is correct
15 Correct 2193 ms 7404 KB Output is correct
16 Correct 660 ms 12440 KB Output is correct
17 Correct 1308 ms 9084 KB Output is correct
18 Correct 1969 ms 12612 KB Output is correct
19 Correct 1755 ms 12824 KB Output is correct
20 Correct 1870 ms 12152 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 532 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 904 ms 27400 KB Output is correct
13 Correct 731 ms 27644 KB Output is correct
14 Correct 900 ms 24604 KB Output is correct
15 Correct 963 ms 24256 KB Output is correct
16 Correct 670 ms 15476 KB Output is correct
17 Correct 968 ms 24520 KB Output is correct
18 Correct 957 ms 24056 KB Output is correct
19 Correct 1399 ms 11752 KB Output is correct
20 Correct 1837 ms 5240 KB Output is correct
21 Correct 653 ms 1228 KB Output is correct
22 Correct 2208 ms 7544 KB Output is correct
23 Correct 632 ms 12280 KB Output is correct
24 Correct 1256 ms 9032 KB Output is correct
25 Correct 2057 ms 12804 KB Output is correct
26 Correct 2001 ms 12700 KB Output is correct
27 Correct 1665 ms 12152 KB Output is correct
28 Correct 820 ms 125740 KB Output is correct
29 Correct 1865 ms 140748 KB Output is correct
30 Correct 4389 ms 101852 KB Output is correct
31 Correct 4233 ms 78072 KB Output is correct
32 Correct 624 ms 1128 KB Output is correct
33 Correct 778 ms 2424 KB Output is correct
34 Correct 506 ms 137848 KB Output is correct
35 Correct 1361 ms 70432 KB Output is correct
36 Correct 2759 ms 138336 KB Output is correct
37 Correct 2119 ms 138296 KB Output is correct
38 Correct 1979 ms 137776 KB Output is correct
39 Correct 1721 ms 106468 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 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 0 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 2 ms 384 KB Output is correct
12 Correct 1036 ms 27488 KB Output is correct
13 Correct 777 ms 27544 KB Output is correct
14 Correct 956 ms 24648 KB Output is correct
15 Correct 1073 ms 24228 KB Output is correct
16 Correct 699 ms 15356 KB Output is correct
17 Correct 1028 ms 24440 KB Output is correct
18 Correct 959 ms 24016 KB Output is correct
19 Correct 1439 ms 11500 KB Output is correct
20 Correct 1875 ms 5052 KB Output is correct
21 Correct 701 ms 1072 KB Output is correct
22 Correct 2319 ms 7312 KB Output is correct
23 Correct 647 ms 12408 KB Output is correct
24 Correct 1316 ms 9104 KB Output is correct
25 Correct 2096 ms 12600 KB Output is correct
26 Correct 1774 ms 12792 KB Output is correct
27 Correct 1850 ms 12120 KB Output is correct
28 Correct 961 ms 125732 KB Output is correct
29 Correct 2021 ms 140720 KB Output is correct
30 Correct 4579 ms 101800 KB Output is correct
31 Correct 4188 ms 77944 KB Output is correct
32 Correct 618 ms 1144 KB Output is correct
33 Correct 825 ms 2424 KB Output is correct
34 Correct 489 ms 137848 KB Output is correct
35 Correct 1348 ms 70408 KB Output is correct
36 Correct 2486 ms 138140 KB Output is correct
37 Correct 2103 ms 138512 KB Output is correct
38 Correct 2190 ms 137708 KB Output is correct
39 Runtime error 1211 ms 256004 KB Execution killed with signal 9
40 Halted 0 ms 0 KB -