oj.uz

Submission #278574

# Submission time Handle Problem Language Result Execution time Memory
278574 2020-08-21T14:44:52 Z _7_7_ Game (IOI13_game) C++14
80 / 100
 4649 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 = 4e5 + 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, n, m, x, y, l, r;
ll z;
               	
ll gcd (ll x, ll y) {
	while (1) {
		if (x > y)
			swap(x, y);
		if (!x)				
			return y;		
//		cerr << x << ' ' << y << endl;
		y %= x;
	}
}

struct ST {
	int l, r, tl, tr;
	ll g;
	ST () {}
	ST (int Tl, int Tr) {
		tl = Tl;
		tr = Tr;
		g = 0;
		l = r = 0;
	}
};

ST T[N];

void upd1 (int pos, ll x, int v) {
	int tl = T[v].tl;
	int tr = T[v].tr;

	if (tl == tr) {
		T[v].g = x;
		return;
	}

	int tm = (tl + tr) >> 1;
	if (pos <= tm) {
		if (!T[v].l)  {
			T[v].l = ++Sz; 
			T[Sz] = ST(tl, tm);
		}
		upd1(pos, x, T[v].l);
	} else {
		if (!T[v].r) {
			T[v].r = ++Sz; 
			T[Sz] = ST(tm + 1, tr);
		}
		upd1(pos, x, T[v].r);
	}

	T[v].g = gcd(T[T[v].l].g, T[T[v].r].g);
}

ll get1 (int l, int r, int v) {
    int tl = T[v].tl, tr = T[v].tr;
	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);

	if (T[v].r)
		res = gcd(res, get1(l, r, T[v].r));

 	return res;
}

ll get2 (int pos, int v) {
    int tl = T[v].tl, tr = T[v].tr;
	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);
	}

	if (!T[v].r)
		return 0;

	return get2(pos, T[v].r);
}


struct STT {
	int l, r, v, tl, tr;
	STT () {
	
	}

	STT (int V, int Tl, int Tr) {
		tl = Tl;
		tr = Tr;
		l = r = 0;		
		v = V;
	}
};

STT TT[maxn];

int Sz1;



void upd (int v) {
    int tl = TT[v].tl, tr = TT[v].tr;
//	cerr << v << ' ' << x << ' ' << y << ' ' << z << ' ' << tl << ' ' << tr << ' ' << TT[v].v << endl;
	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);
//			if (Sz + 1 == N || Sz1 + 1 == maxn) 
//				exit(0);
			TT[v].l = ++Sz1;
			TT[Sz1] = STT(++Sz, tl, tm); 
			T[Sz] = ST(0, inf - 1);
		}
		upd(TT[v].l);
	} else {
		if (!TT[v].r) {
//			assert(Sz + 1 < N);
//			assert(Sz1 + 1 < maxn);
//			if (Sz + 1 == N || Sz1 + 1 == maxn) 
//				exit(0);			
			TT[v].r = ++Sz1;
			TT[Sz1] = STT(++Sz, tm + 1, tr);
			T[Sz] = ST(0, inf - 1);
		}

		upd(TT[v].r);
	}

	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 v) {
    int tl =  TT[v].tl, tr = TT[v].tr;
	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(TT[v].l);

	if (TT[v].r)
		res = gcd(res, get(TT[v].r));

	return res;
}


void init(int r, int c) {
//	assert(0);
	TT[++Sz1] = STT(++Sz, 0, inf - 1);
	T[Sz] = ST(0, inf - 1);
}

void update(int X, int Y, ll Z) {
//	cerr << x << ' ' << y << ' ' << z << endl;
	x = X, y = Y, z = Z;
	upd(1);
//	cerr << Sz << ' ' << Sz1 << endl;
}

long long calculate(int L, int X, int R, int Y) {		
//	cerr << x << ' ' << y << ' ' << lf << ' ' << rg << endl;
	l = L, x = X, r = R, y = Y;
    return get(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;
      |      ^~~
game.cpp: In function 'll get1(int, int, int)':
game.cpp:108:6: warning: unused variable 'tm' [-Wunused-variable]
  108 |  int tm = (tl + tr) >> 1;
      |      ^~
game.cpp: In function 'll get(int)':
game.cpp:213:6: warning: unused variable 'tm' [-Wunused-variable]
  213 |  int tm = (tl + tr) >> 1;
      |      ^~

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 640 KB Output is correct
3 Correct 3 ms 640 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 640 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 3 ms 640 KB Output is correct
10 Correct 2 ms 512 KB Output is correct
11 Correct 2 ms 512 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 1047 ms 43384 KB Output is correct
5 Correct 787 ms 43000 KB Output is correct
6 Correct 1044 ms 40692 KB Output is correct
7 Correct 1130 ms 40432 KB Output is correct
8 Correct 729 ms 26436 KB Output is correct
9 Correct 1094 ms 40656 KB Output is correct
10 Correct 1196 ms 40188 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 640 KB Output is correct
3 Correct 3 ms 640 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 3 ms 616 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 640 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 2 ms 512 KB Output is correct
12 Correct 1574 ms 19428 KB Output is correct
13 Correct 1986 ms 11112 KB Output is correct
14 Correct 654 ms 5752 KB Output is correct
15 Correct 2345 ms 14988 KB Output is correct
16 Correct 723 ms 22136 KB Output is correct
17 Correct 1650 ms 17692 KB Output is correct
18 Correct 2633 ms 23544 KB Output is correct
19 Correct 2314 ms 23668 KB Output is correct
20 Correct 2400 ms 23112 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 640 KB Output is correct
3 Correct 4 ms 640 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 3 ms 640 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 640 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 1031 ms 43256 KB Output is correct
13 Correct 778 ms 43128 KB Output is correct
14 Correct 1010 ms 40824 KB Output is correct
15 Correct 1082 ms 40568 KB Output is correct
16 Correct 725 ms 26488 KB Output is correct
17 Correct 1133 ms 40824 KB Output is correct
18 Correct 1153 ms 40184 KB Output is correct
19 Correct 1611 ms 19308 KB Output is correct
20 Correct 2005 ms 11180 KB Output is correct
21 Correct 667 ms 5848 KB Output is correct
22 Correct 2394 ms 15008 KB Output is correct
23 Correct 697 ms 22124 KB Output is correct
24 Correct 1591 ms 17888 KB Output is correct
25 Correct 2572 ms 23672 KB Output is correct
26 Correct 2220 ms 23800 KB Output is correct
27 Correct 2279 ms 23120 KB Output is correct
28 Correct 966 ms 198776 KB Output is correct
29 Correct 2382 ms 219484 KB Output is correct
30 Correct 4649 ms 159452 KB Output is correct
31 Correct 4372 ms 123768 KB Output is correct
32 Correct 614 ms 10488 KB Output is correct
33 Correct 827 ms 12180 KB Output is correct
34 Correct 551 ms 213240 KB Output is correct
35 Correct 1797 ms 114808 KB Output is correct
36 Correct 3167 ms 217632 KB Output is correct
37 Correct 2627 ms 217532 KB Output is correct
38 Correct 2541 ms 216752 KB Output is correct
39 Correct 2158 ms 169616 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 3 ms 640 KB Output is correct
3 Correct 3 ms 640 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 640 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 640 KB Output is correct
10 Correct 2 ms 512 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 1121 ms 43388 KB Output is correct
13 Correct 807 ms 43260 KB Output is correct
14 Correct 1052 ms 40696 KB Output is correct
15 Correct 1112 ms 40432 KB Output is correct
16 Correct 728 ms 26488 KB Output is correct
17 Correct 1096 ms 40824 KB Output is correct
18 Correct 1052 ms 40364 KB Output is correct
19 Correct 1613 ms 19292 KB Output is correct
20 Correct 2025 ms 11128 KB Output is correct
21 Correct 663 ms 5880 KB Output is correct
22 Correct 2364 ms 15188 KB Output is correct
23 Correct 673 ms 22264 KB Output is correct
24 Correct 1591 ms 17700 KB Output is correct
25 Correct 3103 ms 23612 KB Output is correct
26 Correct 2406 ms 23588 KB Output is correct
27 Correct 2154 ms 23032 KB Output is correct
28 Correct 1002 ms 197860 KB Output is correct
29 Correct 2452 ms 219384 KB Output is correct
30 Correct 4649 ms 159604 KB Output is correct
31 Correct 4401 ms 123500 KB Output is correct
32 Correct 659 ms 10488 KB Output is correct
33 Correct 840 ms 12408 KB Output is correct
34 Correct 558 ms 213496 KB Output is correct
35 Correct 1611 ms 114356 KB Output is correct
36 Correct 3382 ms 215928 KB Output is correct
37 Correct 2748 ms 216200 KB Output is correct
38 Correct 2560 ms 215616 KB Output is correct
39 Runtime error 773 ms 256004 KB Execution killed with signal 9
40 Halted 0 ms 0 KB -