oj.uz

Submission #276867

# Submission time Handle Problem Language Result Execution time Memory
276867 2020-08-20T17:50:41 Z _7_7_ Game (IOI13_game) C++14
63 / 100
 3605 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 = 3e5 + 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 4 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 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 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 1158 ms 73480 KB Output is correct
5 Correct 858 ms 73332 KB Output is correct
6 Correct 1299 ms 70768 KB Output is correct
7 Correct 1277 ms 70292 KB Output is correct
8 Correct 820 ms 42360 KB Output is correct
9 Correct 1217 ms 70936 KB Output is correct
10 Correct 1208 ms 70124 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 0 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 1470 ms 25720 KB Output is correct
13 Correct 1920 ms 12908 KB Output is correct
14 Correct 613 ms 1376 KB Output is correct
15 Correct 2201 ms 19812 KB Output is correct
16 Correct 751 ms 34588 KB Output is correct
17 Correct 1710 ms 23556 KB Output is correct
18 Correct 2851 ms 34772 KB Output is correct
19 Correct 2569 ms 34892 KB Output is correct
20 Correct 2531 ms 34340 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 4 ms 896 KB Output is correct
3 Correct 3 ms 1024 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 2 ms 640 KB Output is correct
11 Correct 1 ms 512 KB Output is correct
12 Correct 1121 ms 73332 KB Output is correct
13 Correct 864 ms 73364 KB Output is correct
14 Correct 1132 ms 70780 KB Output is correct
15 Correct 1193 ms 70400 KB Output is correct
16 Correct 778 ms 42376 KB Output is correct
17 Correct 1248 ms 70796 KB Output is correct
18 Correct 1228 ms 70180 KB Output is correct
19 Correct 1563 ms 25900 KB Output is correct
20 Correct 1882 ms 12968 KB Output is correct
21 Correct 617 ms 1400 KB Output is correct
22 Correct 2182 ms 19704 KB Output is correct
23 Correct 670 ms 34532 KB Output is correct
24 Correct 1825 ms 23544 KB Output is correct
25 Correct 2962 ms 34800 KB Output is correct
26 Correct 2562 ms 35012 KB Output is correct
27 Correct 2438 ms 34356 KB Output is correct
28 Runtime error 762 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 416 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 3 ms 896 KB Output is correct
10 Correct 2 ms 768 KB Output is correct
11 Correct 1 ms 512 KB Output is correct
12 Correct 1175 ms 73312 KB Output is correct
13 Correct 857 ms 73336 KB Output is correct
14 Correct 1177 ms 70676 KB Output is correct
15 Correct 1169 ms 70488 KB Output is correct
16 Correct 774 ms 42368 KB Output is correct
17 Correct 1195 ms 70720 KB Output is correct
18 Correct 1192 ms 70248 KB Output is correct
19 Correct 1557 ms 25912 KB Output is correct
20 Correct 1892 ms 12824 KB Output is correct
21 Correct 619 ms 1400 KB Output is correct
22 Correct 2200 ms 19760 KB Output is correct
23 Correct 674 ms 34552 KB Output is correct
24 Correct 1999 ms 23512 KB Output is correct
25 Correct 3605 ms 34728 KB Output is correct
26 Correct 2644 ms 34924 KB Output is correct
27 Correct 2562 ms 34416 KB Output is correct
28 Runtime error 773 ms 256004 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -