oj.uz

Submission #276866

# Submission time Handle Problem Language Result Execution time Memory
276866 2020-08-20T17:49:11 Z _7_7_ Game (IOI13_game) C++14
63 / 100
 3057 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 = 5e5 + 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 9 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 384 KB Output is correct
5 Correct 1 ms 512 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 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 1191 ms 75640 KB Output is correct
5 Correct 910 ms 75640 KB Output is correct
6 Correct 1231 ms 72980 KB Output is correct
7 Correct 1299 ms 72540 KB Output is correct
8 Correct 970 ms 44844 KB Output is correct
9 Correct 1359 ms 73172 KB Output is correct
10 Correct 1290 ms 71824 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 4 ms 872 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 1581 ms 27352 KB Output is correct
13 Correct 1873 ms 14772 KB Output is correct
14 Correct 611 ms 2936 KB Output is correct
15 Correct 2179 ms 21112 KB Output is correct
16 Correct 703 ms 35712 KB Output is correct
17 Correct 1799 ms 24652 KB Output is correct
18 Correct 2921 ms 36152 KB Output is correct
19 Correct 2498 ms 36004 KB Output is correct
20 Correct 2564 ms 35492 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 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 2 ms 640 KB Output is correct
11 Correct 2 ms 512 KB Output is correct
12 Correct 1112 ms 73676 KB Output is correct
13 Correct 861 ms 73892 KB Output is correct
14 Correct 1160 ms 70976 KB Output is correct
15 Correct 1179 ms 70796 KB Output is correct
16 Correct 848 ms 42840 KB Output is correct
17 Correct 1269 ms 71160 KB Output is correct
18 Correct 1160 ms 70588 KB Output is correct
19 Correct 1494 ms 26208 KB Output is correct
20 Correct 1873 ms 13304 KB Output is correct
21 Correct 611 ms 1784 KB Output is correct
22 Correct 2247 ms 20112 KB Output is correct
23 Correct 708 ms 34968 KB Output is correct
24 Correct 1782 ms 23800 KB Output is correct
25 Correct 2944 ms 35236 KB Output is correct
26 Correct 2497 ms 35316 KB Output is correct
27 Correct 2394 ms 34644 KB Output is correct
28 Runtime error 802 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 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 1 ms 512 KB Output is correct
12 Correct 1126 ms 73340 KB Output is correct
13 Correct 839 ms 73580 KB Output is correct
14 Correct 1122 ms 70776 KB Output is correct
15 Correct 1186 ms 70264 KB Output is correct
16 Correct 781 ms 42444 KB Output is correct
17 Correct 1203 ms 71016 KB Output is correct
18 Correct 1249 ms 70144 KB Output is correct
19 Correct 1538 ms 25720 KB Output is correct
20 Correct 1992 ms 12840 KB Output is correct
21 Correct 619 ms 1488 KB Output is correct
22 Correct 2217 ms 19704 KB Output is correct
23 Correct 679 ms 34552 KB Output is correct
24 Correct 1787 ms 23616 KB Output is correct
25 Correct 3057 ms 34724 KB Output is correct
26 Correct 2854 ms 34968 KB Output is correct
27 Correct 2587 ms 34232 KB Output is correct
28 Runtime error 796 ms 256004 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -