oj.uz

Submission #276921

# Submission time Handle Problem Language Result Execution time Memory
276921 2020-08-20T18:58:15 Z _7_7_ Game (IOI13_game) C++14
80 / 100
 4452 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 + 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 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 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 929 ms 27448 KB Output is correct
5 Correct 746 ms 27640 KB Output is correct
6 Correct 951 ms 24464 KB Output is correct
7 Correct 1004 ms 24224 KB Output is correct
8 Correct 689 ms 15388 KB Output is correct
9 Correct 1002 ms 24388 KB Output is correct
10 Correct 1016 ms 24096 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 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 3 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 2 ms 384 KB Output is correct
12 Correct 1440 ms 11788 KB Output is correct
13 Correct 1875 ms 4984 KB Output is correct
14 Correct 646 ms 1120 KB Output is correct
15 Correct 2208 ms 7368 KB Output is correct
16 Correct 682 ms 12256 KB Output is correct
17 Correct 1466 ms 8944 KB Output is correct
18 Correct 2148 ms 12644 KB Output is correct
19 Correct 1951 ms 12832 KB Output is correct
20 Correct 1803 ms 12100 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 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 950 ms 27480 KB Output is correct
13 Correct 741 ms 27768 KB Output is correct
14 Correct 976 ms 24440 KB Output is correct
15 Correct 1029 ms 24264 KB Output is correct
16 Correct 710 ms 15512 KB Output is correct
17 Correct 952 ms 24480 KB Output is correct
18 Correct 951 ms 24056 KB Output is correct
19 Correct 1393 ms 11608 KB Output is correct
20 Correct 1868 ms 5524 KB Output is correct
21 Correct 677 ms 1056 KB Output is correct
22 Correct 2381 ms 7348 KB Output is correct
23 Correct 653 ms 12232 KB Output is correct
24 Correct 1476 ms 8952 KB Output is correct
25 Correct 2131 ms 12552 KB Output is correct
26 Correct 1943 ms 12868 KB Output is correct
27 Correct 1767 ms 12104 KB Output is correct
28 Correct 875 ms 125560 KB Output is correct
29 Correct 1952 ms 140664 KB Output is correct
30 Correct 4402 ms 101860 KB Output is correct
31 Correct 4146 ms 77944 KB Output is correct
32 Correct 602 ms 1144 KB Output is correct
33 Correct 806 ms 2452 KB Output is correct
34 Correct 494 ms 137764 KB Output is correct
35 Correct 1451 ms 70364 KB Output is correct
36 Correct 2566 ms 138104 KB Output is correct
37 Correct 2133 ms 138256 KB Output is correct
38 Correct 2182 ms 137780 KB Output is correct
39 Correct 1930 ms 106352 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 304 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 945 ms 27512 KB Output is correct
13 Correct 743 ms 27640 KB Output is correct
14 Correct 900 ms 24588 KB Output is correct
15 Correct 982 ms 24312 KB Output is correct
16 Correct 659 ms 15352 KB Output is correct
17 Correct 940 ms 24444 KB Output is correct
18 Correct 1004 ms 24184 KB Output is correct
19 Correct 1496 ms 11580 KB Output is correct
20 Correct 1890 ms 5004 KB Output is correct
21 Correct 659 ms 1016 KB Output is correct
22 Correct 2268 ms 7460 KB Output is correct
23 Correct 645 ms 12404 KB Output is correct
24 Correct 1326 ms 8976 KB Output is correct
25 Correct 2107 ms 12748 KB Output is correct
26 Correct 1994 ms 12696 KB Output is correct
27 Correct 1878 ms 12036 KB Output is correct
28 Correct 870 ms 125688 KB Output is correct
29 Correct 1892 ms 140820 KB Output is correct
30 Correct 4452 ms 101908 KB Output is correct
31 Correct 4156 ms 77976 KB Output is correct
32 Correct 620 ms 1184 KB Output is correct
33 Correct 817 ms 2328 KB Output is correct
34 Correct 510 ms 137804 KB Output is correct
35 Correct 1394 ms 70488 KB Output is correct
36 Correct 2574 ms 138112 KB Output is correct
37 Correct 2227 ms 138364 KB Output is correct
38 Correct 2195 ms 137764 KB Output is correct
39 Runtime error 1189 ms 256004 KB Execution killed with signal 9
40 Halted 0 ms 0 KB -