답안 #278737

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
278737	2020-08-21T17:35:28 Z	_7_7_	게임 (IOI13_game)	C++14	100 / 100	5774 ms	252856 KB

game

#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 = 4e5 + 11, mod = 998244353, N = 1e7 + 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;
int l, r, x, y;
ll z;
               	
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, pos;
	ll g;
};
 
ST T[N];
 
void upd1 (int pos, ll x, int v, int tl = 0, int tr = m - 1) {
//	cerr << v << ' ' << tl << ' ' << tr << ' ' << pos << ' ' << x << endl;
	if (tl == tr) {
		T[v].g = x;
		return;
	}

	if (!T[v].l && !T[v].r && T[v].pos == -1) {
		T[v].pos = pos;
		T[v].g = x;
		return;
	}

	if (T[v].pos != -1) {
		if (T[v].pos == pos) {
			T[v].g = x;
			return;
		}
   		
		int u = T[v].pos;
		T[v].pos = -1;

		T[v].l = ++Sz;
		
		T[v].r = ++Sz;

		upd1(u, T[v].g, v, tl, tr);
	}
 
	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 (T[v].pos != -1) {
    	if (l <= T[v].pos && T[v].pos <= r)
    		return T[v].g;
		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;
}

struct STT {
	int l, r, v;
};
 
STT TT[maxn];
 
int Sz1;
 
 
 
void upd (int v = 1, int tl = 0, int tr = n - 1) {
//	cerr << tl << ' ' << tr << endl;
	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(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(TT[v].r, tm + 1, tr);
	}
 
	ll cur = 0;
	if (TT[v].l) 
		cur = get1(y, y, TT[TT[v].l].v); 
	
	if (TT[v].r)
		cur = gcd(cur, get1(y, y, TT[TT[v].r].v));
 
	upd1(y, cur, TT[v].v);
//	cerr << tl << ' ' << tr << ' ' << cur << endl;
}
 
ll get (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(TT[v].l, tl, tm);
 
	if (TT[v].r)
		res = gcd(res, get(TT[v].r, tm + 1, tr));
 
	return res;
}
 
 
void init(int r, int c) {
	for (int i = 0; i < N; ++i) {
		T[i].pos = -1; 
		T[i].g = 0;
	}

//	assert(0);
	n = r, m = c;
	n = inf, m = inf;
	TT[++Sz1].v = ++Sz;
}
 
void update(int X, int Y, ll Z) {
//	cerr << x << ' ' << y << ' ' << z << endl;
	x = X, y = Y, z = Z;
	upd(1);
//	cerr << Sz << ' ' << Sz1 << endl;
}
 
long long calculate(int L, int X, int R, int Y) {		
//	cerr << x << ' ' << y << ' ' << lf << ' ' << rg << endl;
	l = L, r = R, x = X, y = Y;
    return get(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;
      |      ^~~
game.cpp: In function 'll get1(int, int, int, int, int)':
game.cpp:115:6: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  115 |      if (l <= T[v].pos && T[v].pos <= r)
      |      ^~
game.cpp:117:3: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  117 |   return 0;
      |   ^~~~~~

Subtask #1

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	130 ms	235128 KB	Output is correct
2	Correct	132 ms	235128 KB	Output is correct
3	Correct	132 ms	235128 KB	Output is correct
4	Correct	130 ms	235264 KB	Output is correct
5	Correct	130 ms	235132 KB	Output is correct
6	Correct	130 ms	235128 KB	Output is correct
7	Correct	132 ms	235256 KB	Output is correct
8	Correct	132 ms	235128 KB	Output is correct
9	Correct	129 ms	235128 KB	Output is correct
10	Correct	131 ms	235204 KB	Output is correct
11	Correct	131 ms	235128 KB	Output is correct
12	Correct	130 ms	235128 KB	Output is correct

Subtask #2

27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	131 ms	235128 KB	Output is correct
2	Correct	131 ms	235128 KB	Output is correct
3	Correct	131 ms	235128 KB	Output is correct
4	Correct	1114 ms	243704 KB	Output is correct
5	Correct	957 ms	243448 KB	Output is correct
6	Correct	1067 ms	240848 KB	Output is correct
7	Correct	1199 ms	240672 KB	Output is correct
8	Correct	820 ms	241016 KB	Output is correct
9	Correct	1239 ms	240776 KB	Output is correct
10	Correct	1214 ms	240352 KB	Output is correct
11	Correct	130 ms	235128 KB	Output is correct

Subtask #3

26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	134 ms	235204 KB	Output is correct
2	Correct	132 ms	235228 KB	Output is correct
3	Correct	140 ms	235128 KB	Output is correct
4	Correct	130 ms	235128 KB	Output is correct
5	Correct	128 ms	235128 KB	Output is correct
6	Correct	131 ms	235128 KB	Output is correct
7	Correct	134 ms	235084 KB	Output is correct
8	Correct	130 ms	235156 KB	Output is correct
9	Correct	133 ms	235140 KB	Output is correct
10	Correct	143 ms	235128 KB	Output is correct
11	Correct	136 ms	235128 KB	Output is correct
12	Correct	1961 ms	243320 KB	Output is correct
13	Correct	2437 ms	240156 KB	Output is correct
14	Correct	985 ms	240376 KB	Output is correct
15	Correct	2791 ms	240316 KB	Output is correct
16	Correct	952 ms	240276 KB	Output is correct
17	Correct	1517 ms	241528 KB	Output is correct
18	Correct	2751 ms	241512 KB	Output is correct
19	Correct	2444 ms	241788 KB	Output is correct
20	Correct	2184 ms	241260 KB	Output is correct
21	Correct	132 ms	235128 KB	Output is correct

Subtask #4

17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	132 ms	235128 KB	Output is correct
2	Correct	134 ms	235256 KB	Output is correct
3	Correct	133 ms	235128 KB	Output is correct
4	Correct	131 ms	235128 KB	Output is correct
5	Correct	129 ms	235132 KB	Output is correct
6	Correct	133 ms	235256 KB	Output is correct
7	Correct	129 ms	235128 KB	Output is correct
8	Correct	129 ms	235128 KB	Output is correct
9	Correct	137 ms	235172 KB	Output is correct
10	Correct	132 ms	235128 KB	Output is correct
11	Correct	130 ms	235128 KB	Output is correct
12	Correct	1109 ms	243832 KB	Output is correct
13	Correct	949 ms	243524 KB	Output is correct
14	Correct	1054 ms	240888 KB	Output is correct
15	Correct	1131 ms	240632 KB	Output is correct
16	Correct	816 ms	241144 KB	Output is correct
17	Correct	1158 ms	240684 KB	Output is correct
18	Correct	1127 ms	240376 KB	Output is correct
19	Correct	1805 ms	243448 KB	Output is correct
20	Correct	2303 ms	239992 KB	Output is correct
21	Correct	967 ms	240504 KB	Output is correct
22	Correct	2700 ms	240376 KB	Output is correct
23	Correct	972 ms	240164 KB	Output is correct
24	Correct	1642 ms	241400 KB	Output is correct
25	Correct	2642 ms	241596 KB	Output is correct
26	Correct	2231 ms	241684 KB	Output is correct
27	Correct	2128 ms	241144 KB	Output is correct
28	Correct	864 ms	243952 KB	Output is correct
29	Correct	1649 ms	247420 KB	Output is correct
30	Correct	4780 ms	243832 KB	Output is correct
31	Correct	4612 ms	243704 KB	Output is correct
32	Correct	921 ms	242760 KB	Output is correct
33	Correct	1073 ms	242808 KB	Output is correct
34	Correct	427 ms	244676 KB	Output is correct
35	Correct	1066 ms	244208 KB	Output is correct
36	Correct	2495 ms	244472 KB	Output is correct
37	Correct	1840 ms	244840 KB	Output is correct
38	Correct	1681 ms	244344 KB	Output is correct
39	Correct	1422 ms	244472 KB	Output is correct
40	Correct	126 ms	235128 KB	Output is correct

Subtask #5

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	122 ms	235128 KB	Output is correct
2	Correct	129 ms	235128 KB	Output is correct
3	Correct	145 ms	235200 KB	Output is correct
4	Correct	133 ms	235196 KB	Output is correct
5	Correct	133 ms	235184 KB	Output is correct
6	Correct	132 ms	235128 KB	Output is correct
7	Correct	132 ms	235128 KB	Output is correct
8	Correct	136 ms	235144 KB	Output is correct
9	Correct	138 ms	235132 KB	Output is correct
10	Correct	130 ms	235160 KB	Output is correct
11	Correct	132 ms	235128 KB	Output is correct
12	Correct	1192 ms	243620 KB	Output is correct
13	Correct	1022 ms	243576 KB	Output is correct
14	Correct	1117 ms	240892 KB	Output is correct
15	Correct	1194 ms	240632 KB	Output is correct
16	Correct	830 ms	241016 KB	Output is correct
17	Correct	1225 ms	240736 KB	Output is correct
18	Correct	1167 ms	240448 KB	Output is correct
19	Correct	1873 ms	243380 KB	Output is correct
20	Correct	2381 ms	239944 KB	Output is correct
21	Correct	985 ms	240436 KB	Output is correct
22	Correct	2780 ms	240376 KB	Output is correct
23	Correct	959 ms	240248 KB	Output is correct
24	Correct	1580 ms	241400 KB	Output is correct
25	Correct	2746 ms	241724 KB	Output is correct
26	Correct	2537 ms	241856 KB	Output is correct
27	Correct	2223 ms	241204 KB	Output is correct
28	Correct	911 ms	244916 KB	Output is correct
29	Correct	1588 ms	249512 KB	Output is correct
30	Correct	4704 ms	244048 KB	Output is correct
31	Correct	4496 ms	243888 KB	Output is correct
32	Correct	936 ms	243696 KB	Output is correct
33	Correct	1102 ms	243868 KB	Output is correct
34	Correct	411 ms	244856 KB	Output is correct
35	Correct	1088 ms	245172 KB	Output is correct
36	Correct	2242 ms	247752 KB	Output is correct
37	Correct	1627 ms	247788 KB	Output is correct
38	Correct	1661 ms	247140 KB	Output is correct
39	Correct	1150 ms	250644 KB	Output is correct
40	Correct	2460 ms	252856 KB	Output is correct
41	Correct	5774 ms	245648 KB	Output is correct
42	Correct	5488 ms	245204 KB	Output is correct
43	Correct	639 ms	247620 KB	Output is correct
44	Correct	1310 ms	245372 KB	Output is correct
45	Correct	1426 ms	248568 KB	Output is correct
46	Correct	2609 ms	251564 KB	Output is correct
47	Correct	2736 ms	251488 KB	Output is correct
48	Correct	2646 ms	251120 KB	Output is correct
49	Correct	122 ms	235128 KB	Output is correct