oj.uz

Submission #276925

# Submission time Handle Problem Language Result Execution time Memory
276925 2020-08-20T19:02:07 Z _7_7_ Game (IOI13_game) C++14
80 / 100
 4420 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 = 2e6 + 11, mod = 998244353, N = 1e7 + 7e6 + 5e5 + 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 3 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 0 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 994 ms 27376 KB Output is correct
5 Correct 844 ms 27520 KB Output is correct
6 Correct 935 ms 24488 KB Output is correct
7 Correct 1087 ms 24184 KB Output is correct
8 Correct 674 ms 15480 KB Output is correct
9 Correct 999 ms 24420 KB Output is correct
10 Correct 956 ms 24056 KB Output is correct
11 Correct 0 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 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 0 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 1515 ms 11672 KB Output is correct
13 Correct 1979 ms 5052 KB Output is correct
14 Correct 663 ms 1064 KB Output is correct
15 Correct 2185 ms 7408 KB Output is correct
16 Correct 656 ms 12432 KB Output is correct
17 Correct 1314 ms 8952 KB Output is correct
18 Correct 2212 ms 12556 KB Output is correct
19 Correct 1985 ms 12716 KB Output is correct
20 Correct 1811 ms 12108 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 0 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 938 ms 27520 KB Output is correct
13 Correct 754 ms 27636 KB Output is correct
14 Correct 922 ms 24552 KB Output is correct
15 Correct 989 ms 24168 KB Output is correct
16 Correct 717 ms 15608 KB Output is correct
17 Correct 1087 ms 24552 KB Output is correct
18 Correct 1002 ms 23964 KB Output is correct
19 Correct 1447 ms 11520 KB Output is correct
20 Correct 1893 ms 5004 KB Output is correct
21 Correct 675 ms 1144 KB Output is correct
22 Correct 2213 ms 7304 KB Output is correct
23 Correct 644 ms 12284 KB Output is correct
24 Correct 1376 ms 9080 KB Output is correct
25 Correct 2124 ms 12536 KB Output is correct
26 Correct 1863 ms 12776 KB Output is correct
27 Correct 1827 ms 12116 KB Output is correct
28 Correct 838 ms 125816 KB Output is correct
29 Correct 1945 ms 140760 KB Output is correct
30 Correct 4420 ms 101880 KB Output is correct
31 Correct 4112 ms 77944 KB Output is correct
32 Correct 652 ms 1112 KB Output is correct
33 Correct 761 ms 2564 KB Output is correct
34 Correct 512 ms 137976 KB Output is correct
35 Correct 1434 ms 70392 KB Output is correct
36 Correct 2478 ms 138324 KB Output is correct
37 Correct 2058 ms 138392 KB Output is correct
38 Correct 1968 ms 137920 KB Output is correct
39 Correct 1687 ms 106428 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 640 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 988 ms 27400 KB Output is correct
13 Correct 809 ms 27628 KB Output is correct
14 Correct 917 ms 24624 KB Output is correct
15 Correct 965 ms 24336 KB Output is correct
16 Correct 665 ms 15628 KB Output is correct
17 Correct 954 ms 24476 KB Output is correct
18 Correct 899 ms 24044 KB Output is correct
19 Correct 1413 ms 11768 KB Output is correct
20 Correct 1861 ms 5240 KB Output is correct
21 Correct 633 ms 1076 KB Output is correct
22 Correct 2185 ms 7416 KB Output is correct
23 Correct 630 ms 12212 KB Output is correct
24 Correct 1263 ms 9080 KB Output is correct
25 Correct 2128 ms 12760 KB Output is correct
26 Correct 1847 ms 12852 KB Output is correct
27 Correct 1639 ms 12320 KB Output is correct
28 Correct 811 ms 125688 KB Output is correct
29 Correct 1883 ms 140960 KB Output is correct
30 Correct 4308 ms 101976 KB Output is correct
31 Correct 4223 ms 77988 KB Output is correct
32 Correct 590 ms 1112 KB Output is correct
33 Correct 815 ms 2288 KB Output is correct
34 Correct 545 ms 137840 KB Output is correct
35 Correct 1443 ms 70516 KB Output is correct
36 Correct 2413 ms 138164 KB Output is correct
37 Correct 2076 ms 138596 KB Output is correct
38 Correct 2033 ms 137796 KB Output is correct
39 Runtime error 1250 ms 256004 KB Execution killed with signal 9
40 Halted 0 ms 0 KB -