oj.uz

Submission #278368

# Submission time Handle Problem Language Result Execution time Memory
278368 2020-08-21T12:12:58 Z _7_7_ Game (IOI13_game) C++11
80 / 100
 4328 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 = 3e5 + 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;
               	
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;
	ll g;
};

ST T[N];

void upd1 (int pos, ll x, int v, int tl = 0, int tr = m - 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 = m - 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 = m - 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 = n - 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);
//			if (Sz + 1 == N || Sz1 + 1 == maxn) 
//				exit(0);
			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);
//			if (Sz + 1 == N || Sz1 + 1 == maxn) 
//				exit(0);			
			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 = n - 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 r, int c) {
//	assert(0);
	n = r, m = c;
	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 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 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 256 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 703 ms 8484 KB Output is correct
5 Correct 521 ms 8864 KB Output is correct
6 Correct 576 ms 5700 KB Output is correct
7 Correct 757 ms 5464 KB Output is correct
8 Correct 421 ms 4328 KB Output is correct
9 Correct 613 ms 5504 KB Output is correct
10 Correct 551 ms 5096 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 1 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 992 ms 10160 KB Output is correct
13 Correct 1459 ms 3704 KB Output is correct
14 Correct 316 ms 920 KB Output is correct
15 Correct 1754 ms 5088 KB Output is correct
16 Correct 218 ms 9720 KB Output is correct
17 Correct 804 ms 6524 KB Output is correct
18 Correct 1322 ms 9932 KB Output is correct
19 Correct 1085 ms 10360 KB Output is correct
20 Correct 1056 ms 9464 KB Output is correct
21 Correct 1 ms 256 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 288 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 599 ms 8632 KB Output is correct
13 Correct 445 ms 8828 KB Output is correct
14 Correct 480 ms 5700 KB Output is correct
15 Correct 532 ms 5496 KB Output is correct
16 Correct 419 ms 4320 KB Output is correct
17 Correct 685 ms 5468 KB Output is correct
18 Correct 547 ms 5232 KB Output is correct
19 Correct 1120 ms 10080 KB Output is correct
20 Correct 1512 ms 3656 KB Output is correct
21 Correct 351 ms 888 KB Output is correct
22 Correct 1811 ms 5152 KB Output is correct
23 Correct 217 ms 9720 KB Output is correct
24 Correct 852 ms 6652 KB Output is correct
25 Correct 1536 ms 10068 KB Output is correct
26 Correct 1421 ms 10148 KB Output is correct
27 Correct 1085 ms 9596 KB Output is correct
28 Correct 796 ms 125688 KB Output is correct
29 Correct 2123 ms 140748 KB Output is correct
30 Correct 4328 ms 101856 KB Output is correct
31 Correct 4089 ms 77944 KB Output is correct
32 Correct 583 ms 1056 KB Output is correct
33 Correct 929 ms 2532 KB Output is correct
34 Correct 511 ms 137808 KB Output is correct
35 Correct 1392 ms 70372 KB Output is correct
36 Correct 2584 ms 138260 KB Output is correct
37 Correct 2295 ms 138364 KB Output is correct
38 Correct 2322 ms 137728 KB Output is correct
39 Correct 1869 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 0 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 1 ms 288 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 712 ms 8568 KB Output is correct
13 Correct 501 ms 8800 KB Output is correct
14 Correct 583 ms 5796 KB Output is correct
15 Correct 621 ms 5520 KB Output is correct
16 Correct 429 ms 4344 KB Output is correct
17 Correct 594 ms 5524 KB Output is correct
18 Correct 593 ms 5116 KB Output is correct
19 Correct 1136 ms 10128 KB Output is correct
20 Correct 1595 ms 3572 KB Output is correct
21 Correct 373 ms 940 KB Output is correct
22 Correct 1819 ms 4856 KB Output is correct
23 Correct 244 ms 9720 KB Output is correct
24 Correct 951 ms 6608 KB Output is correct
25 Correct 1657 ms 9952 KB Output is correct
26 Correct 1508 ms 10168 KB Output is correct
27 Correct 1071 ms 9564 KB Output is correct
28 Correct 947 ms 125604 KB Output is correct
29 Correct 1936 ms 140788 KB Output is correct
30 Correct 4144 ms 101852 KB Output is correct
31 Correct 4014 ms 77928 KB Output is correct
32 Correct 591 ms 1100 KB Output is correct
33 Correct 794 ms 2428 KB Output is correct
34 Correct 559 ms 137848 KB Output is correct
35 Correct 1464 ms 70372 KB Output is correct
36 Correct 2719 ms 138104 KB Output is correct
37 Correct 2222 ms 138336 KB Output is correct
38 Correct 2443 ms 137720 KB Output is correct
39 Runtime error 1356 ms 256000 KB Execution killed with signal 11
40 Halted 0 ms 0 KB -