oj.uz

Submission #276859

# Submission time Handle Problem Language Result Execution time Memory
276859 2020-08-20T17:45:52 Z _7_7_ Game (IOI13_game) C++14
63 / 100
 3506 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 = 1e6 + 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 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 3 ms 768 KB Output is correct
10 Correct 1 ms 640 KB Output is correct
11 Correct 1 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 1128 ms 77688 KB Output is correct
5 Correct 857 ms 77300 KB Output is correct
6 Correct 1202 ms 75376 KB Output is correct
7 Correct 1255 ms 75144 KB Output is correct
8 Correct 824 ms 46652 KB Output is correct
9 Correct 1211 ms 75512 KB Output is correct
10 Correct 1169 ms 75232 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 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 2 ms 896 KB Output is correct
10 Correct 1 ms 640 KB Output is correct
11 Correct 2 ms 512 KB Output is correct
12 Correct 1514 ms 29820 KB Output is correct
13 Correct 1944 ms 17024 KB Output is correct
14 Correct 621 ms 6076 KB Output is correct
15 Correct 2232 ms 24260 KB Output is correct
16 Correct 729 ms 38748 KB Output is correct
17 Correct 1884 ms 28584 KB Output is correct
18 Correct 3170 ms 40440 KB Output is correct
19 Correct 2552 ms 40412 KB Output is correct
20 Correct 2498 ms 39744 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 376 KB Output is correct
2 Correct 3 ms 888 KB Output is correct
3 Correct 3 ms 896 KB Output is correct
4 Correct 1 ms 376 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 1 ms 640 KB Output is correct
11 Correct 1 ms 512 KB Output is correct
12 Correct 1095 ms 77816 KB Output is correct
13 Correct 907 ms 77304 KB Output is correct
14 Correct 1141 ms 75288 KB Output is correct
15 Correct 1226 ms 75000 KB Output is correct
16 Correct 785 ms 46584 KB Output is correct
17 Correct 1182 ms 75384 KB Output is correct
18 Correct 1178 ms 74788 KB Output is correct
19 Correct 1522 ms 29848 KB Output is correct
20 Correct 1936 ms 16756 KB Output is correct
21 Correct 624 ms 6096 KB Output is correct
22 Correct 2200 ms 24040 KB Output is correct
23 Correct 705 ms 38684 KB Output is correct
24 Correct 1913 ms 28344 KB Output is correct
25 Correct 3357 ms 40060 KB Output is correct
26 Correct 2856 ms 40308 KB Output is correct
27 Correct 2857 ms 39760 KB Output is correct
28 Runtime error 918 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 4 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 376 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 3 ms 896 KB Output is correct
10 Correct 1 ms 640 KB Output is correct
11 Correct 1 ms 512 KB Output is correct
12 Correct 1214 ms 77748 KB Output is correct
13 Correct 986 ms 77344 KB Output is correct
14 Correct 1286 ms 75216 KB Output is correct
15 Correct 1307 ms 74968 KB Output is correct
16 Correct 864 ms 46584 KB Output is correct
17 Correct 1382 ms 75408 KB Output is correct
18 Correct 1471 ms 74848 KB Output is correct
19 Correct 1680 ms 29916 KB Output is correct
20 Correct 2072 ms 16920 KB Output is correct
21 Correct 714 ms 6008 KB Output is correct
22 Correct 2450 ms 24084 KB Output is correct
23 Correct 772 ms 38748 KB Output is correct
24 Correct 2328 ms 28304 KB Output is correct
25 Correct 3506 ms 40108 KB Output is correct
26 Correct 2997 ms 40304 KB Output is correct
27 Correct 2702 ms 39560 KB Output is correct
28 Runtime error 859 ms 256004 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -