oj.uz

Submission #276905

# Submission time Handle Problem Language Result Execution time Memory
276905 2020-08-20T18:34:36 Z _7_7_ Game (IOI13_game) C++14
80 / 100
 4419 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 = 1e7 + 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 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 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 416 KB Output is correct
4 Correct 921 ms 27460 KB Output is correct
5 Correct 741 ms 27740 KB Output is correct
6 Correct 894 ms 24440 KB Output is correct
7 Correct 1041 ms 24440 KB Output is correct
8 Correct 664 ms 15392 KB Output is correct
9 Correct 959 ms 24524 KB Output is correct
10 Correct 884 ms 24056 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 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 2 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1381 ms 11796 KB Output is correct
13 Correct 1834 ms 5112 KB Output is correct
14 Correct 652 ms 1156 KB Output is correct
15 Correct 2146 ms 7356 KB Output is correct
16 Correct 628 ms 12280 KB Output is correct
17 Correct 1294 ms 9144 KB Output is correct
18 Correct 2095 ms 12744 KB Output is correct
19 Correct 1919 ms 13000 KB Output is correct
20 Correct 1772 ms 12072 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 2 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 3 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 933 ms 27440 KB Output is correct
13 Correct 719 ms 27616 KB Output is correct
14 Correct 904 ms 24460 KB Output is correct
15 Correct 959 ms 24244 KB Output is correct
16 Correct 693 ms 15404 KB Output is correct
17 Correct 1010 ms 24568 KB Output is correct
18 Correct 910 ms 24020 KB Output is correct
19 Correct 1377 ms 11668 KB Output is correct
20 Correct 1875 ms 5292 KB Output is correct
21 Correct 626 ms 1016 KB Output is correct
22 Correct 2206 ms 7400 KB Output is correct
23 Correct 636 ms 12280 KB Output is correct
24 Correct 1328 ms 8952 KB Output is correct
25 Correct 2059 ms 12692 KB Output is correct
26 Correct 1891 ms 12664 KB Output is correct
27 Correct 1727 ms 12152 KB Output is correct
28 Correct 862 ms 127480 KB Output is correct
29 Correct 1971 ms 150888 KB Output is correct
30 Correct 4324 ms 109176 KB Output is correct
31 Correct 4081 ms 85228 KB Output is correct
32 Correct 574 ms 10360 KB Output is correct
33 Correct 748 ms 11536 KB Output is correct
34 Correct 481 ms 144632 KB Output is correct
35 Correct 1340 ms 80144 KB Output is correct
36 Correct 2512 ms 149044 KB Output is correct
37 Correct 2117 ms 149004 KB Output is correct
38 Correct 2258 ms 148416 KB Output is correct
39 Correct 1984 ms 116656 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 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 2 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 947 ms 27560 KB Output is correct
13 Correct 760 ms 27512 KB Output is correct
14 Correct 894 ms 24604 KB Output is correct
15 Correct 958 ms 24552 KB Output is correct
16 Correct 676 ms 15368 KB Output is correct
17 Correct 970 ms 24444 KB Output is correct
18 Correct 901 ms 24196 KB Output is correct
19 Correct 1473 ms 11528 KB Output is correct
20 Correct 1947 ms 5060 KB Output is correct
21 Correct 638 ms 1144 KB Output is correct
22 Correct 2188 ms 7336 KB Output is correct
23 Correct 671 ms 12336 KB Output is correct
24 Correct 1352 ms 9088 KB Output is correct
25 Correct 2164 ms 12624 KB Output is correct
26 Correct 1870 ms 12896 KB Output is correct
27 Correct 1709 ms 12376 KB Output is correct
28 Correct 860 ms 128472 KB Output is correct
29 Correct 2020 ms 151080 KB Output is correct
30 Correct 4419 ms 108884 KB Output is correct
31 Correct 4207 ms 85112 KB Output is correct
32 Correct 592 ms 10360 KB Output is correct
33 Correct 756 ms 11556 KB Output is correct
34 Correct 498 ms 144632 KB Output is correct
35 Correct 1321 ms 80152 KB Output is correct
36 Correct 2420 ms 148784 KB Output is correct
37 Correct 2084 ms 149060 KB Output is correct
38 Correct 2107 ms 148316 KB Output is correct
39 Runtime error 857 ms 256000 KB Execution killed with signal 11
40 Halted 0 ms 0 KB -