oj.uz

Submission #278254

# Submission time Handle Problem Language Result Execution time Memory
278254 2020-08-21T11:29:31 Z _7_7_ Game (IOI13_game) C++14
80 / 100
 4826 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 = 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);
//	cerr << Sz << ' ' << Sz1 << endl;
}

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 488 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 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 959 ms 31904 KB Output is correct
5 Correct 754 ms 31524 KB Output is correct
6 Correct 947 ms 29136 KB Output is correct
7 Correct 959 ms 28936 KB Output is correct
8 Correct 687 ms 19804 KB Output is correct
9 Correct 961 ms 29104 KB Output is correct
10 Correct 969 ms 28680 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 0 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 512 KB Output is correct
9 Correct 2 ms 640 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 1452 ms 15996 KB Output is correct
13 Correct 1877 ms 9080 KB Output is correct
14 Correct 682 ms 5896 KB Output is correct
15 Correct 2212 ms 11888 KB Output is correct
16 Correct 664 ms 16672 KB Output is correct
17 Correct 1439 ms 13872 KB Output is correct
18 Correct 2403 ms 17804 KB Output is correct
19 Correct 1859 ms 18040 KB Output is correct
20 Correct 1660 ms 17400 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 930 ms 31904 KB Output is correct
13 Correct 735 ms 31480 KB Output is correct
14 Correct 1000 ms 29172 KB Output is correct
15 Correct 1079 ms 28820 KB Output is correct
16 Correct 772 ms 19696 KB Output is correct
17 Correct 1014 ms 29068 KB Output is correct
18 Correct 954 ms 28664 KB Output is correct
19 Correct 1432 ms 15672 KB Output is correct
20 Correct 1861 ms 9464 KB Output is correct
21 Correct 641 ms 5760 KB Output is correct
22 Correct 2267 ms 11756 KB Output is correct
23 Correct 753 ms 16568 KB Output is correct
24 Correct 1484 ms 13944 KB Output is correct
25 Correct 2094 ms 17992 KB Output is correct
26 Correct 1758 ms 18108 KB Output is correct
27 Correct 1769 ms 17588 KB Output is correct
28 Correct 876 ms 136164 KB Output is correct
29 Correct 2031 ms 150996 KB Output is correct
30 Correct 4406 ms 109084 KB Output is correct
31 Correct 4100 ms 85152 KB Output is correct
32 Correct 598 ms 10416 KB Output is correct
33 Correct 765 ms 11512 KB Output is correct
34 Correct 508 ms 144516 KB Output is correct
35 Correct 1427 ms 80120 KB Output is correct
36 Correct 2428 ms 148776 KB Output is correct
37 Correct 2035 ms 148912 KB Output is correct
38 Correct 2114 ms 148320 KB Output is correct
39 Correct 1839 ms 116732 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 1 ms 256 KB Output is correct
6 Correct 2 ms 544 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 2 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 994 ms 31924 KB Output is correct
13 Correct 746 ms 31532 KB Output is correct
14 Correct 924 ms 29140 KB Output is correct
15 Correct 986 ms 28924 KB Output is correct
16 Correct 670 ms 19960 KB Output is correct
17 Correct 950 ms 29304 KB Output is correct
18 Correct 944 ms 28652 KB Output is correct
19 Correct 1581 ms 15580 KB Output is correct
20 Correct 1972 ms 8924 KB Output is correct
21 Correct 708 ms 5760 KB Output is correct
22 Correct 2219 ms 11820 KB Output is correct
23 Correct 692 ms 16636 KB Output is correct
24 Correct 1350 ms 13916 KB Output is correct
25 Correct 2207 ms 18144 KB Output is correct
26 Correct 1823 ms 18028 KB Output is correct
27 Correct 1911 ms 17348 KB Output is correct
28 Correct 843 ms 136272 KB Output is correct
29 Correct 1968 ms 150852 KB Output is correct
30 Correct 4826 ms 108836 KB Output is correct
31 Correct 4181 ms 85132 KB Output is correct
32 Correct 633 ms 10652 KB Output is correct
33 Correct 771 ms 11768 KB Output is correct
34 Correct 527 ms 144540 KB Output is correct
35 Correct 1432 ms 80424 KB Output is correct
36 Correct 2696 ms 148860 KB Output is correct
37 Correct 2285 ms 149012 KB Output is correct
38 Correct 2282 ms 148352 KB Output is correct
39 Runtime error 1239 ms 256004 KB Execution killed with signal 9
40 Halted 0 ms 0 KB -