oj.uz

Submission #276915

# Submission time Handle Problem Language Result Execution time Memory
276915 2020-08-20T18:49:03 Z _7_7_ Game (IOI13_game) C++14
80 / 100
 4520 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 = 1e6 + 11, mod = 998244353, N = 2e7 + 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 504 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 8 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 938 ms 28872 KB Output is correct
5 Correct 726 ms 28792 KB Output is correct
6 Correct 907 ms 25976 KB Output is correct
7 Correct 1026 ms 25592 KB Output is correct
8 Correct 658 ms 16708 KB Output is correct
9 Correct 968 ms 25920 KB Output is correct
10 Correct 954 ms 25312 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 372 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1376 ms 12920 KB Output is correct
13 Correct 1848 ms 6208 KB Output is correct
14 Correct 637 ms 2300 KB Output is correct
15 Correct 2195 ms 8648 KB Output is correct
16 Correct 702 ms 13276 KB Output is correct
17 Correct 1323 ms 10332 KB Output is correct
18 Correct 2085 ms 13888 KB Output is correct
19 Correct 1812 ms 14200 KB Output is correct
20 Correct 1656 ms 13432 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 926 ms 28596 KB Output is correct
13 Correct 719 ms 28792 KB Output is correct
14 Correct 907 ms 25924 KB Output is correct
15 Correct 940 ms 25732 KB Output is correct
16 Correct 655 ms 16632 KB Output is correct
17 Correct 941 ms 25828 KB Output is correct
18 Correct 935 ms 25332 KB Output is correct
19 Correct 1394 ms 12872 KB Output is correct
20 Correct 1874 ms 6228 KB Output is correct
21 Correct 685 ms 2680 KB Output is correct
22 Correct 2202 ms 8780 KB Output is correct
23 Correct 630 ms 13560 KB Output is correct
24 Correct 1356 ms 10540 KB Output is correct
25 Correct 2121 ms 14120 KB Output is correct
26 Correct 1738 ms 14308 KB Output is correct
27 Correct 1649 ms 13440 KB Output is correct
28 Correct 803 ms 126968 KB Output is correct
29 Correct 1935 ms 141168 KB Output is correct
30 Correct 4349 ms 101944 KB Output is correct
31 Correct 4053 ms 78252 KB Output is correct
32 Correct 584 ms 1132 KB Output is correct
33 Correct 765 ms 2312 KB Output is correct
34 Correct 488 ms 137916 KB Output is correct
35 Correct 1301 ms 70364 KB Output is correct
36 Correct 2400 ms 138380 KB Output is correct
37 Correct 2183 ms 138616 KB Output is correct
38 Correct 2103 ms 138032 KB Output is correct
39 Correct 1706 ms 106488 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 921 ms 27476 KB Output is correct
13 Correct 729 ms 27704 KB Output is correct
14 Correct 932 ms 24596 KB Output is correct
15 Correct 1006 ms 24300 KB Output is correct
16 Correct 670 ms 15608 KB Output is correct
17 Correct 967 ms 24384 KB Output is correct
18 Correct 930 ms 23912 KB Output is correct
19 Correct 1396 ms 11640 KB Output is correct
20 Correct 1849 ms 5068 KB Output is correct
21 Correct 672 ms 1040 KB Output is correct
22 Correct 2206 ms 7432 KB Output is correct
23 Correct 657 ms 12248 KB Output is correct
24 Correct 1349 ms 9004 KB Output is correct
25 Correct 2111 ms 12612 KB Output is correct
26 Correct 1960 ms 12780 KB Output is correct
27 Correct 1901 ms 12336 KB Output is correct
28 Correct 851 ms 125688 KB Output is correct
29 Correct 2043 ms 140880 KB Output is correct
30 Correct 4520 ms 101900 KB Output is correct
31 Correct 4121 ms 78032 KB Output is correct
32 Correct 593 ms 1272 KB Output is correct
33 Correct 773 ms 2424 KB Output is correct
34 Correct 497 ms 137848 KB Output is correct
35 Correct 1564 ms 70456 KB Output is correct
36 Correct 2770 ms 138376 KB Output is correct
37 Correct 2231 ms 138348 KB Output is correct
38 Correct 2247 ms 137708 KB Output is correct
39 Runtime error 1243 ms 256004 KB Execution killed with signal 9
40 Halted 0 ms 0 KB -