oj.uz

답안 #278361

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
278361 2020-08-21T12:10:15 Z _7_7_ 게임 (IOI13_game) C++17
80 / 100
 4131 ms 256000 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 = 3e5 + 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;
               	
ll gcd (ll x, ll y) {
	while (1) {
		if (x > y)
			swap(x, y);
		if (!x)				
			return y;		
//		cerr << x << ' ' << y << endl;
		y %= x;
	}
}

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);
//			if (Sz + 1 == N || Sz1 + 1 == maxn) 
//				exit(0);
			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);
//			if (Sz + 1 == N || Sz1 + 1 == maxn) 
//				exit(0);			
			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 0 ms 256 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 256 KB Output is correct
5 Correct 1 ms 256 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 0 ms 256 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 586 ms 8696 KB Output is correct
5 Correct 442 ms 8952 KB Output is correct
6 Correct 515 ms 5708 KB Output is correct
7 Correct 547 ms 5496 KB Output is correct
8 Correct 432 ms 4472 KB Output is correct
9 Correct 537 ms 5624 KB Output is correct
10 Correct 492 ms 5112 KB Output is correct
11 Correct 0 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 0 ms 384 KB Output is correct
5 Correct 1 ms 256 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 1061 ms 10232 KB Output is correct
13 Correct 1712 ms 3592 KB Output is correct
14 Correct 352 ms 1008 KB Output is correct
15 Correct 1891 ms 4872 KB Output is correct
16 Correct 226 ms 9720 KB Output is correct
17 Correct 814 ms 6772 KB Output is correct
18 Correct 1428 ms 9952 KB Output is correct
19 Correct 1108 ms 10232 KB Output is correct
20 Correct 1027 ms 9540 KB Output is correct
21 Correct 0 ms 256 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 512 KB Output is correct
3 Correct 1 ms 416 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 256 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 512 KB Output is correct
12 Correct 609 ms 8568 KB Output is correct
13 Correct 447 ms 8824 KB Output is correct
14 Correct 493 ms 5692 KB Output is correct
15 Correct 571 ms 5496 KB Output is correct
16 Correct 382 ms 4352 KB Output is correct
17 Correct 535 ms 5668 KB Output is correct
18 Correct 499 ms 5112 KB Output is correct
19 Correct 947 ms 10300 KB Output is correct
20 Correct 1494 ms 3848 KB Output is correct
21 Correct 311 ms 1020 KB Output is correct
22 Correct 1748 ms 5004 KB Output is correct
23 Correct 222 ms 9720 KB Output is correct
24 Correct 818 ms 6692 KB Output is correct
25 Correct 1452 ms 10104 KB Output is correct
26 Correct 1136 ms 10232 KB Output is correct
27 Correct 1024 ms 9720 KB Output is correct
28 Correct 829 ms 125688 KB Output is correct
29 Correct 1893 ms 140800 KB Output is correct
30 Correct 4131 ms 102044 KB Output is correct
31 Correct 3800 ms 78244 KB Output is correct
32 Correct 590 ms 1144 KB Output is correct
33 Correct 748 ms 2424 KB Output is correct
34 Correct 492 ms 137956 KB Output is correct
35 Correct 1426 ms 70448 KB Output is correct
36 Correct 2525 ms 138264 KB Output is correct
37 Correct 2025 ms 138480 KB Output is correct
38 Correct 2221 ms 137796 KB Output is correct
39 Correct 2278 ms 106352 KB Output is correct
40 Correct 1 ms 256 KB Output is correct

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 256 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 256 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 712 ms 8532 KB Output is correct
13 Correct 512 ms 8824 KB Output is correct
14 Correct 529 ms 5720 KB Output is correct
15 Correct 584 ms 5496 KB Output is correct
16 Correct 381 ms 4464 KB Output is correct
17 Correct 593 ms 5496 KB Output is correct
18 Correct 521 ms 5120 KB Output is correct
19 Correct 975 ms 10104 KB Output is correct
20 Correct 1492 ms 3764 KB Output is correct
21 Correct 323 ms 1060 KB Output is correct
22 Correct 1818 ms 5048 KB Output is correct
23 Correct 226 ms 9720 KB Output is correct
24 Correct 873 ms 6520 KB Output is correct
25 Correct 1459 ms 10116 KB Output is correct
26 Correct 1176 ms 10316 KB Output is correct
27 Correct 1066 ms 9536 KB Output is correct
28 Correct 800 ms 125688 KB Output is correct
29 Correct 2033 ms 140744 KB Output is correct
30 Correct 4018 ms 101896 KB Output is correct
31 Correct 3743 ms 78468 KB Output is correct
32 Correct 579 ms 1240 KB Output is correct
33 Correct 739 ms 2296 KB Output is correct
34 Correct 564 ms 137848 KB Output is correct
35 Correct 1369 ms 70540 KB Output is correct
36 Correct 2397 ms 138556 KB Output is correct
37 Correct 2015 ms 138488 KB Output is correct
38 Correct 2097 ms 138116 KB Output is correct
39 Runtime error 1308 ms 256000 KB Execution killed with signal 11
40 Halted 0 ms 0 KB -