oj.uz

Submission #276919

# Submission time Handle Problem Language Result Execution time Memory
276919 2020-08-20T18:55:15 Z _7_7_ Game (IOI13_game) C++14
80 / 100
 4305 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 = 4e6 + 11, mod = 998244353, N = 1e7 + 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 524 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 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 950 ms 27444 KB Output is correct
5 Correct 782 ms 27592 KB Output is correct
6 Correct 1010 ms 24584 KB Output is correct
7 Correct 1072 ms 24264 KB Output is correct
8 Correct 686 ms 15464 KB Output is correct
9 Correct 987 ms 24444 KB Output is correct
10 Correct 947 ms 24088 KB Output is correct
11 Correct 0 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 1435 ms 11668 KB Output is correct
13 Correct 1966 ms 5104 KB Output is correct
14 Correct 655 ms 1144 KB Output is correct
15 Correct 2210 ms 7336 KB Output is correct
16 Correct 679 ms 12316 KB Output is correct
17 Correct 1361 ms 8980 KB Output is correct
18 Correct 2083 ms 12612 KB Output is correct
19 Correct 1776 ms 12744 KB Output is correct
20 Correct 1874 ms 12228 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 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 938 ms 27384 KB Output is correct
13 Correct 736 ms 27544 KB Output is correct
14 Correct 939 ms 24536 KB Output is correct
15 Correct 1010 ms 24316 KB Output is correct
16 Correct 681 ms 15348 KB Output is correct
17 Correct 1008 ms 24568 KB Output is correct
18 Correct 996 ms 24184 KB Output is correct
19 Correct 1426 ms 11644 KB Output is correct
20 Correct 1846 ms 5140 KB Output is correct
21 Correct 634 ms 1016 KB Output is correct
22 Correct 2247 ms 7392 KB Output is correct
23 Correct 645 ms 12280 KB Output is correct
24 Correct 1306 ms 8992 KB Output is correct
25 Correct 2119 ms 12680 KB Output is correct
26 Correct 1943 ms 12820 KB Output is correct
27 Correct 1752 ms 12096 KB Output is correct
28 Correct 880 ms 125640 KB Output is correct
29 Correct 1951 ms 140784 KB Output is correct
30 Correct 4305 ms 101880 KB Output is correct
31 Correct 4138 ms 77944 KB Output is correct
32 Correct 578 ms 1144 KB Output is correct
33 Correct 762 ms 2356 KB Output is correct
34 Correct 530 ms 137848 KB Output is correct
35 Correct 1398 ms 70392 KB Output is correct
36 Correct 2518 ms 138408 KB Output is correct
37 Correct 2107 ms 138360 KB Output is correct
38 Correct 2070 ms 137832 KB Output is correct
39 Correct 1916 ms 106520 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 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 945 ms 27492 KB Output is correct
13 Correct 733 ms 27512 KB Output is correct
14 Correct 962 ms 24588 KB Output is correct
15 Correct 957 ms 24312 KB Output is correct
16 Correct 701 ms 15480 KB Output is correct
17 Correct 990 ms 24824 KB Output is correct
18 Correct 951 ms 24184 KB Output is correct
19 Correct 1375 ms 11764 KB Output is correct
20 Correct 1867 ms 5048 KB Output is correct
21 Correct 637 ms 1252 KB Output is correct
22 Correct 2168 ms 7492 KB Output is correct
23 Correct 639 ms 12308 KB Output is correct
24 Correct 1321 ms 9100 KB Output is correct
25 Correct 2031 ms 12544 KB Output is correct
26 Correct 1828 ms 12668 KB Output is correct
27 Correct 1665 ms 12048 KB Output is correct
28 Correct 894 ms 125776 KB Output is correct
29 Correct 1941 ms 140792 KB Output is correct
30 Correct 4290 ms 101940 KB Output is correct
31 Correct 4129 ms 78052 KB Output is correct
32 Correct 608 ms 1272 KB Output is correct
33 Correct 792 ms 2396 KB Output is correct
34 Correct 570 ms 137848 KB Output is correct
35 Correct 1518 ms 70424 KB Output is correct
36 Correct 2602 ms 138104 KB Output is correct
37 Correct 2277 ms 138364 KB Output is correct
38 Correct 2072 ms 137664 KB Output is correct
39 Runtime error 1625 ms 256000 KB Execution killed with signal 11
40 Halted 0 ms 0 KB -