oj.uz

Submission #276918

# Submission time Handle Problem Language Result Execution time Memory
276918 2020-08-20T18:54:12 Z _7_7_ Game (IOI13_game) C++14
80 / 100
 4463 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 = 2e7 + 6e6 + 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 3 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 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 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 923 ms 27380 KB Output is correct
5 Correct 737 ms 27640 KB Output is correct
6 Correct 928 ms 24568 KB Output is correct
7 Correct 1047 ms 24320 KB Output is correct
8 Correct 733 ms 15484 KB Output is correct
9 Correct 1042 ms 24596 KB Output is correct
10 Correct 894 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 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 1390 ms 11640 KB Output is correct
13 Correct 1858 ms 5240 KB Output is correct
14 Correct 630 ms 1144 KB Output is correct
15 Correct 2171 ms 7560 KB Output is correct
16 Correct 631 ms 12420 KB Output is correct
17 Correct 1372 ms 9208 KB Output is correct
18 Correct 2052 ms 13036 KB Output is correct
19 Correct 1745 ms 12920 KB Output is correct
20 Correct 1667 ms 12288 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 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 0 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 962 ms 27488 KB Output is correct
13 Correct 793 ms 27660 KB Output is correct
14 Correct 1026 ms 24568 KB Output is correct
15 Correct 986 ms 24312 KB Output is correct
16 Correct 700 ms 15444 KB Output is correct
17 Correct 966 ms 24440 KB Output is correct
18 Correct 953 ms 24080 KB Output is correct
19 Correct 1383 ms 11712 KB Output is correct
20 Correct 1834 ms 5016 KB Output is correct
21 Correct 636 ms 1016 KB Output is correct
22 Correct 2171 ms 7364 KB Output is correct
23 Correct 680 ms 12348 KB Output is correct
24 Correct 1308 ms 8952 KB Output is correct
25 Correct 1978 ms 12736 KB Output is correct
26 Correct 1744 ms 12840 KB Output is correct
27 Correct 1800 ms 12336 KB Output is correct
28 Correct 864 ms 125560 KB Output is correct
29 Correct 1926 ms 140908 KB Output is correct
30 Correct 4342 ms 102100 KB Output is correct
31 Correct 4119 ms 78224 KB Output is correct
32 Correct 602 ms 1132 KB Output is correct
33 Correct 789 ms 2408 KB Output is correct
34 Correct 528 ms 137792 KB Output is correct
35 Correct 1386 ms 70408 KB Output is correct
36 Correct 2744 ms 138220 KB Output is correct
37 Correct 2113 ms 138360 KB Output is correct
38 Correct 2077 ms 137896 KB Output is correct
39 Correct 1786 ms 106292 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 360 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 959 ms 27384 KB Output is correct
13 Correct 750 ms 27504 KB Output is correct
14 Correct 939 ms 24824 KB Output is correct
15 Correct 1020 ms 24248 KB Output is correct
16 Correct 691 ms 15548 KB Output is correct
17 Correct 981 ms 24636 KB Output is correct
18 Correct 947 ms 23928 KB Output is correct
19 Correct 1414 ms 11532 KB Output is correct
20 Correct 1882 ms 5132 KB Output is correct
21 Correct 676 ms 992 KB Output is correct
22 Correct 2224 ms 7324 KB Output is correct
23 Correct 690 ms 12220 KB Output is correct
24 Correct 1311 ms 9080 KB Output is correct
25 Correct 2078 ms 12572 KB Output is correct
26 Correct 1946 ms 12680 KB Output is correct
27 Correct 1877 ms 12248 KB Output is correct
28 Correct 861 ms 125608 KB Output is correct
29 Correct 1946 ms 140820 KB Output is correct
30 Correct 4463 ms 101944 KB Output is correct
31 Correct 4166 ms 77976 KB Output is correct
32 Correct 597 ms 1188 KB Output is correct
33 Correct 759 ms 2492 KB Output is correct
34 Correct 496 ms 137812 KB Output is correct
35 Correct 1329 ms 70268 KB Output is correct
36 Correct 2838 ms 138196 KB Output is correct
37 Correct 2148 ms 138360 KB Output is correct
38 Correct 2088 ms 137852 KB Output is correct
39 Runtime error 1240 ms 256004 KB Execution killed with signal 9
40 Halted 0 ms 0 KB -