oj.uz

Submission #276913

# Submission time Handle Problem Language Result Execution time Memory
276913 2020-08-20T18:45:09 Z _7_7_ Game (IOI13_game) C++14
80 / 100
 4437 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 + 3e6 + 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 384 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 1 ms 288 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 989 ms 27828 KB Output is correct
5 Correct 773 ms 28024 KB Output is correct
6 Correct 974 ms 25156 KB Output is correct
7 Correct 982 ms 24824 KB Output is correct
8 Correct 664 ms 15912 KB Output is correct
9 Correct 962 ms 24952 KB Output is correct
10 Correct 960 ms 24440 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 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 1455 ms 12120 KB Output is correct
13 Correct 1878 ms 5496 KB Output is correct
14 Correct 634 ms 1528 KB Output is correct
15 Correct 2183 ms 7844 KB Output is correct
16 Correct 636 ms 12664 KB Output is correct
17 Correct 1264 ms 9476 KB Output is correct
18 Correct 2235 ms 13020 KB Output is correct
19 Correct 1792 ms 13100 KB Output is correct
20 Correct 1715 ms 12456 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 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 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 928 ms 28020 KB Output is correct
13 Correct 747 ms 28036 KB Output is correct
14 Correct 927 ms 25080 KB Output is correct
15 Correct 1006 ms 24768 KB Output is correct
16 Correct 654 ms 15992 KB Output is correct
17 Correct 989 ms 25020 KB Output is correct
18 Correct 961 ms 24696 KB Output is correct
19 Correct 1407 ms 12280 KB Output is correct
20 Correct 1926 ms 5528 KB Output is correct
21 Correct 660 ms 1676 KB Output is correct
22 Correct 2215 ms 8276 KB Output is correct
23 Correct 653 ms 12920 KB Output is correct
24 Correct 1326 ms 9644 KB Output is correct
25 Correct 2056 ms 13404 KB Output is correct
26 Correct 2005 ms 13520 KB Output is correct
27 Correct 1737 ms 12900 KB Output is correct
28 Correct 807 ms 126336 KB Output is correct
29 Correct 1899 ms 141128 KB Output is correct
30 Correct 4437 ms 103176 KB Output is correct
31 Correct 4123 ms 79048 KB Output is correct
32 Correct 581 ms 2168 KB Output is correct
33 Correct 766 ms 3448 KB Output is correct
34 Correct 508 ms 139016 KB Output is correct
35 Correct 1424 ms 71440 KB Output is correct
36 Correct 2564 ms 139128 KB Output is correct
37 Correct 2169 ms 139504 KB Output is correct
38 Correct 2077 ms 139256 KB Output is correct
39 Correct 1893 ms 107772 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 956 ms 27836 KB Output is correct
13 Correct 766 ms 28156 KB Output is correct
14 Correct 990 ms 24824 KB Output is correct
15 Correct 1040 ms 24564 KB Output is correct
16 Correct 677 ms 15764 KB Output is correct
17 Correct 1039 ms 24920 KB Output is correct
18 Correct 1016 ms 24276 KB Output is correct
19 Correct 1425 ms 12036 KB Output is correct
20 Correct 1831 ms 5368 KB Output is correct
21 Correct 656 ms 1396 KB Output is correct
22 Correct 2208 ms 7660 KB Output is correct
23 Correct 677 ms 12536 KB Output is correct
24 Correct 1463 ms 9296 KB Output is correct
25 Correct 2225 ms 12932 KB Output is correct
26 Correct 1960 ms 13048 KB Output is correct
27 Correct 1808 ms 12516 KB Output is correct
28 Correct 927 ms 126100 KB Output is correct
29 Correct 2020 ms 141228 KB Output is correct
30 Correct 4410 ms 102760 KB Output is correct
31 Correct 4165 ms 78636 KB Output is correct
32 Correct 596 ms 1656 KB Output is correct
33 Correct 761 ms 3192 KB Output is correct
34 Correct 516 ms 138404 KB Output is correct
35 Correct 1469 ms 70968 KB Output is correct
36 Correct 3086 ms 138760 KB Output is correct
37 Correct 2459 ms 138980 KB Output is correct
38 Correct 2247 ms 138384 KB Output is correct
39 Runtime error 1251 ms 256000 KB Execution killed with signal 11
40 Halted 0 ms 0 KB -