oj.uz

Submission #276861

# Submission time Handle Problem Language Result Execution time Memory
276861 2020-08-20T17:46:56 Z _7_7_ Game (IOI13_game) C++14
63 / 100
 3576 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 = 2e5 + 48, mod = 998244353, N = 4e6 + 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 {
	ST *l, *r;
	int tl, tr;
	ll g;
	
	ST () {}
	ST (int lf, int rg) {
		tl = lf;
		tr = rg;
		g = 0;
		l = r = NULL;
	}
	
	void update (int pos, ll x) {
		if (tl == tr) {
		    g = x;
			return;
		}
		

		int tm = (tl + tr) >> 1;
		if (pos <= tm) {
			if (!l)
				l = new ST(tl, tm);
			l->update(pos, x);
		} else {
			if (!r)
				r = new ST(tm + 1, tr);
			r->update(pos, x);
		}

		g = __gcd(!r ? 0 : r->g, !l ? 0 : l->g);
	}

	ll get (int lf, int rg) {
		if (lf > rg || tl > rg || lf > tr)
			return 0;

		if (lf <= tl && tr <= rg) 
			return g;
				
		ll res = 0;
		if (l)	
			res = l->get(lf, rg);

		if (r)
			res = __gcd(res, r->get(lf, rg));

		return res;
	}
	
	ll get1 (int pos) {
		if (tl == tr)
			return g;

		int tm = (tl + tr) >> 1;
		if (pos <= tm) {
			if (!l)
				return 0;
			return l->get1(pos);
		}

		if (!r)
			return 0;

		return r->get1(pos);
	}


};


struct STT {
	int l, r;
	ST *T;
};

STT TT[N];


void New (int v) {
	assert(v < N);
	TT[v].T = new ST(0, inf - 1);
	TT[v].l = TT[v].r = 0;
}


void upd (int x, int y, ll z, int v = 1, int tl = 0, int tr = inf - 1) {
	if (tl == tr)  {
		TT[v].T->update(y, z);	
		return; 
	}
	

	int tm = (tl + tr) >> 1;
	if (x <= tm) {
		if (!TT[v].l) {
			TT[v].l = ++Sz;
			New(Sz);	
		}
		upd(x, y, z, TT[v].l, tl, tm);
	} else {
		if (!TT[v].r) {
			TT[v].r = ++Sz;
			New(Sz);
		} 
		upd(x, y, z, TT[v].r, tm + 1, tr);
	}

	ll cur = 0;

	if (TT[v].l)
		cur = TT[TT[v].l].T->get1(y);

	if (TT[v].r)
		cur = __gcd(cur, TT[TT[v].r].T->get1(y));

	TT[v].T->update(y, cur);
}

ll get (int l, int r, int x, int y, int v = 1, int tl = 0, int tr = inf - 1) {
	if (l > r || l > tr || tl > r)
		return 0;

	if (l <= tl && tr <= r) {
//		cerr << v << ' ' << tl << ' ' << tr << ' ' << x << ' ' << y << ' ' << TT[v].T->get(x, y) << endl;
		return TT[v].T->get(x, y); 
	}

	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) {
	New(++Sz);
}

void update(int x, int y, ll z) {
//	cerr << x << ' ' << y << ' ' << z << endl;
	upd(x, y, z);
}

long long calculate(int lf, int x, int rg, int y) {		
//	cerr << x << ' ' << y << ' ' << lf << ' ' << rg << endl;
    return get(lf, rg, x, y);
}

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 3 ms 896 KB Output is correct
3 Correct 4 ms 896 KB Output is correct
4 Correct 1 ms 416 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 3 ms 896 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 3 ms 896 KB Output is correct
10 Correct 2 ms 640 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 380 KB Output is correct
4 Correct 1191 ms 73760 KB Output is correct
5 Correct 919 ms 73976 KB Output is correct
6 Correct 1381 ms 71352 KB Output is correct
7 Correct 1356 ms 71268 KB Output is correct
8 Correct 874 ms 43368 KB Output is correct
9 Correct 1351 ms 72004 KB Output is correct
10 Correct 1307 ms 71692 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 372 KB Output is correct
2 Correct 3 ms 896 KB Output is correct
3 Correct 3 ms 896 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 896 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 896 KB Output is correct
10 Correct 2 ms 640 KB Output is correct
11 Correct 2 ms 488 KB Output is correct
12 Correct 1722 ms 27232 KB Output is correct
13 Correct 2101 ms 14484 KB Output is correct
14 Correct 794 ms 2836 KB Output is correct
15 Correct 2424 ms 21380 KB Output is correct
16 Correct 798 ms 36216 KB Output is correct
17 Correct 2012 ms 25228 KB Output is correct
18 Correct 3576 ms 36544 KB Output is correct
19 Correct 3060 ms 36724 KB Output is correct
20 Correct 2885 ms 36204 KB Output is correct
21 Correct 1 ms 384 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 3 ms 896 KB Output is correct
3 Correct 3 ms 896 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 896 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 4 ms 896 KB Output is correct
10 Correct 2 ms 640 KB Output is correct
11 Correct 2 ms 512 KB Output is correct
12 Correct 1488 ms 75416 KB Output is correct
13 Correct 910 ms 75520 KB Output is correct
14 Correct 1229 ms 72708 KB Output is correct
15 Correct 1439 ms 72504 KB Output is correct
16 Correct 909 ms 44508 KB Output is correct
17 Correct 1397 ms 73056 KB Output is correct
18 Correct 1364 ms 72424 KB Output is correct
19 Correct 1623 ms 27944 KB Output is correct
20 Correct 1990 ms 15020 KB Output is correct
21 Correct 630 ms 3592 KB Output is correct
22 Correct 2317 ms 21936 KB Output is correct
23 Correct 704 ms 36684 KB Output is correct
24 Correct 1769 ms 25696 KB Output is correct
25 Correct 3021 ms 36976 KB Output is correct
26 Correct 2793 ms 37136 KB Output is correct
27 Correct 2619 ms 36388 KB Output is correct
28 Runtime error 914 ms 256004 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 3 ms 896 KB Output is correct
3 Correct 3 ms 896 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 896 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 896 KB Output is correct
10 Correct 2 ms 640 KB Output is correct
11 Correct 1 ms 512 KB Output is correct
12 Correct 1314 ms 75420 KB Output is correct
13 Correct 1091 ms 75384 KB Output is correct
14 Correct 1224 ms 72260 KB Output is correct
15 Correct 1327 ms 71900 KB Output is correct
16 Correct 819 ms 43604 KB Output is correct
17 Correct 1308 ms 71844 KB Output is correct
18 Correct 1273 ms 71188 KB Output is correct
19 Correct 1626 ms 27000 KB Output is correct
20 Correct 1950 ms 13988 KB Output is correct
21 Correct 626 ms 2572 KB Output is correct
22 Correct 2246 ms 20452 KB Output is correct
23 Correct 691 ms 35292 KB Output is correct
24 Correct 2070 ms 24296 KB Output is correct
25 Correct 3452 ms 35704 KB Output is correct
26 Correct 2524 ms 35688 KB Output is correct
27 Correct 2654 ms 35116 KB Output is correct
28 Runtime error 791 ms 256004 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -