oj.uz

Submission #276924

# Submission time Handle Problem Language Result Execution time Memory
276924 2020-08-20T19:01:02 Z _7_7_ Game (IOI13_game) C++14
80 / 100
 4572 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 + 7e6 + 3e5 + 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 2 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 965 ms 27404 KB Output is correct
5 Correct 785 ms 27632 KB Output is correct
6 Correct 1046 ms 24568 KB Output is correct
7 Correct 980 ms 24440 KB Output is correct
8 Correct 684 ms 15548 KB Output is correct
9 Correct 1010 ms 24440 KB Output is correct
10 Correct 926 ms 23928 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 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 1393 ms 11688 KB Output is correct
13 Correct 1894 ms 5080 KB Output is correct
14 Correct 647 ms 1144 KB Output is correct
15 Correct 2283 ms 7572 KB Output is correct
16 Correct 690 ms 12364 KB Output is correct
17 Correct 1322 ms 8952 KB Output is correct
18 Correct 2316 ms 12584 KB Output is correct
19 Correct 1864 ms 12668 KB Output is correct
20 Correct 1890 ms 12152 KB Output is correct
21 Correct 1 ms 416 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 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 972 ms 27436 KB Output is correct
13 Correct 844 ms 27516 KB Output is correct
14 Correct 964 ms 24468 KB Output is correct
15 Correct 1000 ms 24268 KB Output is correct
16 Correct 676 ms 15464 KB Output is correct
17 Correct 971 ms 24552 KB Output is correct
18 Correct 952 ms 24012 KB Output is correct
19 Correct 1386 ms 11472 KB Output is correct
20 Correct 1860 ms 5012 KB Output is correct
21 Correct 682 ms 1100 KB Output is correct
22 Correct 2238 ms 7320 KB Output is correct
23 Correct 665 ms 12412 KB Output is correct
24 Correct 1532 ms 9128 KB Output is correct
25 Correct 2276 ms 12800 KB Output is correct
26 Correct 1962 ms 12872 KB Output is correct
27 Correct 1757 ms 12048 KB Output is correct
28 Correct 977 ms 125560 KB Output is correct
29 Correct 2001 ms 140844 KB Output is correct
30 Correct 4324 ms 101988 KB Output is correct
31 Correct 4338 ms 78008 KB Output is correct
32 Correct 611 ms 1256 KB Output is correct
33 Correct 769 ms 2384 KB Output is correct
34 Correct 519 ms 137872 KB Output is correct
35 Correct 1480 ms 70384 KB Output is correct
36 Correct 2608 ms 138192 KB Output is correct
37 Correct 2148 ms 138340 KB Output is correct
38 Correct 2209 ms 137744 KB Output is correct
39 Correct 2001 ms 106360 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 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 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 942 ms 27460 KB Output is correct
13 Correct 724 ms 27512 KB Output is correct
14 Correct 979 ms 24440 KB Output is correct
15 Correct 977 ms 24312 KB Output is correct
16 Correct 686 ms 15480 KB Output is correct
17 Correct 1082 ms 24416 KB Output is correct
18 Correct 1016 ms 24000 KB Output is correct
19 Correct 1424 ms 11640 KB Output is correct
20 Correct 1954 ms 4972 KB Output is correct
21 Correct 665 ms 1096 KB Output is correct
22 Correct 2232 ms 7260 KB Output is correct
23 Correct 656 ms 12280 KB Output is correct
24 Correct 1356 ms 9024 KB Output is correct
25 Correct 2353 ms 12504 KB Output is correct
26 Correct 1939 ms 12912 KB Output is correct
27 Correct 1715 ms 12096 KB Output is correct
28 Correct 914 ms 125612 KB Output is correct
29 Correct 1947 ms 140856 KB Output is correct
30 Correct 4572 ms 101832 KB Output is correct
31 Correct 4219 ms 77972 KB Output is correct
32 Correct 626 ms 1100 KB Output is correct
33 Correct 774 ms 2372 KB Output is correct
34 Correct 500 ms 137848 KB Output is correct
35 Correct 1393 ms 70388 KB Output is correct
36 Correct 2718 ms 138104 KB Output is correct
37 Correct 2092 ms 138316 KB Output is correct
38 Correct 1973 ms 137980 KB Output is correct
39 Runtime error 1166 ms 256004 KB Execution killed with signal 9
40 Halted 0 ms 0 KB -