oj.uz

답안 #278267

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
278267 2020-08-21T11:33:18 Z _7_7_ 게임 (IOI13_game) C++14
80 / 100
 4548 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 = 1e6 + 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;

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);
			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);
			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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 416 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 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 384 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 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 608 ms 12980 KB Output is correct
5 Correct 488 ms 12792 KB Output is correct
6 Correct 484 ms 10284 KB Output is correct
7 Correct 525 ms 10232 KB Output is correct
8 Correct 391 ms 8568 KB Output is correct
9 Correct 531 ms 10204 KB Output is correct
10 Correct 501 ms 9720 KB Output is correct
11 Correct 1 ms 384 KB Output is correct

Subtask #3
26.0 / 26.0

# 결과 실행 시간 메모리 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 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 416 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 973 ms 14320 KB Output is correct
13 Correct 1563 ms 7640 KB Output is correct
14 Correct 317 ms 5624 KB Output is correct
15 Correct 1853 ms 9532 KB Output is correct
16 Correct 229 ms 13948 KB Output is correct
17 Correct 878 ms 11504 KB Output is correct
18 Correct 1512 ms 15384 KB Output is correct
19 Correct 1265 ms 15508 KB Output is correct
20 Correct 1192 ms 14944 KB Output is correct
21 Correct 1 ms 384 KB Output is correct

Subtask #4
17.0 / 17.0

# 결과 실행 시간 메모리 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 384 KB Output is correct
5 Correct 1 ms 384 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 596 ms 12972 KB Output is correct
13 Correct 512 ms 12816 KB Output is correct
14 Correct 503 ms 10488 KB Output is correct
15 Correct 594 ms 10156 KB Output is correct
16 Correct 427 ms 8568 KB Output is correct
17 Correct 530 ms 10360 KB Output is correct
18 Correct 516 ms 9812 KB Output is correct
19 Correct 956 ms 14456 KB Output is correct
20 Correct 1531 ms 7696 KB Output is correct
21 Correct 339 ms 5700 KB Output is correct
22 Correct 2102 ms 9336 KB Output is correct
23 Correct 325 ms 13944 KB Output is correct
24 Correct 883 ms 11396 KB Output is correct
25 Correct 1601 ms 15332 KB Output is correct
26 Correct 1330 ms 15484 KB Output is correct
27 Correct 1299 ms 14884 KB Output is correct
28 Correct 918 ms 130808 KB Output is correct
29 Correct 1970 ms 145648 KB Output is correct
30 Correct 4548 ms 106932 KB Output is correct
31 Correct 4118 ms 83000 KB Output is correct
32 Correct 589 ms 6264 KB Output is correct
33 Correct 753 ms 7416 KB Output is correct
34 Correct 489 ms 142328 KB Output is correct
35 Correct 1430 ms 74800 KB Output is correct
36 Correct 2792 ms 142544 KB Output is correct
37 Correct 2298 ms 142656 KB Output is correct
38 Correct 2211 ms 142016 KB Output is correct
39 Correct 1719 ms 110500 KB Output is correct
40 Correct 1 ms 384 KB Output is correct

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 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 1 ms 384 KB Output is correct
5 Correct 1 ms 384 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 613 ms 12792 KB Output is correct
13 Correct 441 ms 12992 KB Output is correct
14 Correct 488 ms 9976 KB Output is correct
15 Correct 535 ms 9720 KB Output is correct
16 Correct 398 ms 8568 KB Output is correct
17 Correct 527 ms 9752 KB Output is correct
18 Correct 474 ms 9336 KB Output is correct
19 Correct 974 ms 14356 KB Output is correct
20 Correct 1593 ms 7708 KB Output is correct
21 Correct 322 ms 5240 KB Output is correct
22 Correct 1832 ms 9408 KB Output is correct
23 Correct 229 ms 13944 KB Output is correct
24 Correct 832 ms 11000 KB Output is correct
25 Correct 1397 ms 14336 KB Output is correct
26 Correct 1167 ms 14492 KB Output is correct
27 Correct 1052 ms 14064 KB Output is correct
28 Correct 826 ms 128884 KB Output is correct
29 Correct 1901 ms 144000 KB Output is correct
30 Correct 4490 ms 104760 KB Output is correct
31 Correct 4066 ms 80860 KB Output is correct
32 Correct 580 ms 4088 KB Output is correct
33 Correct 808 ms 5412 KB Output is correct
34 Correct 512 ms 140408 KB Output is correct
35 Correct 1512 ms 72908 KB Output is correct
36 Correct 2577 ms 140424 KB Output is correct
37 Correct 2270 ms 140652 KB Output is correct
38 Correct 2621 ms 140260 KB Output is correct
39 Runtime error 1351 ms 256004 KB Execution killed with signal 9
40 Halted 0 ms 0 KB -