oj.uz

Submission #276923

# Submission time Handle Problem Language Result Execution time Memory
276923 2020-08-20T18:59:46 Z _7_7_ Game (IOI13_game) C++14
80 / 100
 4425 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 + 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 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 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 960 ms 27576 KB Output is correct
5 Correct 742 ms 27616 KB Output is correct
6 Correct 945 ms 24588 KB Output is correct
7 Correct 1004 ms 24188 KB Output is correct
8 Correct 682 ms 15480 KB Output is correct
9 Correct 1004 ms 24568 KB Output is correct
10 Correct 1080 ms 24080 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 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 1437 ms 11660 KB Output is correct
13 Correct 1854 ms 5120 KB Output is correct
14 Correct 640 ms 1280 KB Output is correct
15 Correct 2162 ms 7356 KB Output is correct
16 Correct 675 ms 12408 KB Output is correct
17 Correct 1352 ms 9096 KB Output is correct
18 Correct 2043 ms 12824 KB Output is correct
19 Correct 2007 ms 12688 KB Output is correct
20 Correct 1888 ms 12064 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 3 ms 544 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 935 ms 27532 KB Output is correct
13 Correct 736 ms 27596 KB Output is correct
14 Correct 943 ms 24484 KB Output is correct
15 Correct 1016 ms 24156 KB Output is correct
16 Correct 759 ms 15608 KB Output is correct
17 Correct 1173 ms 24472 KB Output is correct
18 Correct 1056 ms 23928 KB Output is correct
19 Correct 1403 ms 11624 KB Output is correct
20 Correct 1955 ms 5004 KB Output is correct
21 Correct 640 ms 1144 KB Output is correct
22 Correct 2171 ms 7376 KB Output is correct
23 Correct 627 ms 12280 KB Output is correct
24 Correct 1266 ms 9164 KB Output is correct
25 Correct 1973 ms 12644 KB Output is correct
26 Correct 1774 ms 12724 KB Output is correct
27 Correct 1753 ms 12168 KB Output is correct
28 Correct 898 ms 125640 KB Output is correct
29 Correct 1912 ms 140752 KB Output is correct
30 Correct 4326 ms 102156 KB Output is correct
31 Correct 4066 ms 78048 KB Output is correct
32 Correct 584 ms 1092 KB Output is correct
33 Correct 768 ms 2476 KB Output is correct
34 Correct 515 ms 137936 KB Output is correct
35 Correct 1350 ms 70388 KB Output is correct
36 Correct 2563 ms 138400 KB Output is correct
37 Correct 2088 ms 138436 KB Output is correct
38 Correct 2113 ms 137760 KB Output is correct
39 Correct 1809 ms 106324 KB Output is correct
40 Correct 0 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 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 964 ms 27452 KB Output is correct
13 Correct 768 ms 27560 KB Output is correct
14 Correct 940 ms 24652 KB Output is correct
15 Correct 998 ms 24360 KB Output is correct
16 Correct 689 ms 15608 KB Output is correct
17 Correct 1020 ms 24440 KB Output is correct
18 Correct 937 ms 24116 KB Output is correct
19 Correct 1403 ms 11604 KB Output is correct
20 Correct 1858 ms 5236 KB Output is correct
21 Correct 641 ms 1272 KB Output is correct
22 Correct 2215 ms 7460 KB Output is correct
23 Correct 707 ms 12236 KB Output is correct
24 Correct 1365 ms 9148 KB Output is correct
25 Correct 2209 ms 12748 KB Output is correct
26 Correct 2055 ms 12732 KB Output is correct
27 Correct 1811 ms 12128 KB Output is correct
28 Correct 879 ms 125616 KB Output is correct
29 Correct 1967 ms 140764 KB Output is correct
30 Correct 4425 ms 102052 KB Output is correct
31 Correct 4080 ms 77980 KB Output is correct
32 Correct 593 ms 1144 KB Output is correct
33 Correct 766 ms 2636 KB Output is correct
34 Correct 510 ms 137976 KB Output is correct
35 Correct 1452 ms 70336 KB Output is correct
36 Correct 2639 ms 138160 KB Output is correct
37 Correct 2246 ms 138356 KB Output is correct
38 Correct 2105 ms 137700 KB Output is correct
39 Runtime error 1197 ms 256004 KB Execution killed with signal 9
40 Halted 0 ms 0 KB -