제출 #278574

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
278574		_7_7_	게임 (IOI13_game)	C++14	80 / 100	4649 ms	256004 KiB

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 + 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, x, y, l, r;
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, tl, tr;
	ll g;
	ST () {}
	ST (int Tl, int Tr) {
		tl = Tl;
		tr = Tr;
		g = 0;
		l = r = 0;
	}
};

ST T[N];

void upd1 (int pos, ll x, int v) {
	int tl = T[v].tl;
	int tr = T[v].tr;

	if (tl == tr) {
		T[v].g = x;
		return;
	}

	int tm = (tl + tr) >> 1;
	if (pos <= tm) {
		if (!T[v].l)  {
			T[v].l = ++Sz; 
			T[Sz] = ST(tl, tm);
		}
		upd1(pos, x, T[v].l);
	} else {
		if (!T[v].r) {
			T[v].r = ++Sz; 
			T[Sz] = ST(tm + 1, tr);
		}
		upd1(pos, x, T[v].r);
	}

	T[v].g = gcd(T[T[v].l].g, T[T[v].r].g);
}

ll get1 (int l, int r, int v) {
    int tl = T[v].tl, tr = T[v].tr;
	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);

	if (T[v].r)
		res = gcd(res, get1(l, r, T[v].r));

 	return res;
}

ll get2 (int pos, int v) {
    int tl = T[v].tl, tr = T[v].tr;
	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);
	}

	if (!T[v].r)
		return 0;

	return get2(pos, T[v].r);
}


struct STT {
	int l, r, v, tl, tr;
	STT () {
	
	}

	STT (int V, int Tl, int Tr) {
		tl = Tl;
		tr = Tr;
		l = r = 0;		
		v = V;
	}
};

STT TT[maxn];

int Sz1;



void upd (int v) {
    int tl = TT[v].tl, tr = TT[v].tr;
//	cerr << v << ' ' << x << ' ' << y << ' ' << z << ' ' << tl << ' ' << tr << ' ' << TT[v].v << 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] = STT(++Sz, tl, tm); 
			T[Sz] = ST(0, inf - 1);
		}
		upd(TT[v].l);
	} 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] = STT(++Sz, tm + 1, tr);
			T[Sz] = ST(0, inf - 1);
		}

		upd(TT[v].r);
	}

	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 v) {
    int tl =  TT[v].tl, tr = TT[v].tr;
	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);

	if (TT[v].r)
		res = gcd(res, get(TT[v].r));

	return res;
}


void init(int r, int c) {
//	assert(0);
	TT[++Sz1] = STT(++Sz, 0, inf - 1);
	T[Sz] = ST(0, inf - 1);
}

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, x = X, r = R, y = Y;
    return get(1);
}

컴파일 시 표준 에러 (stderr) 메시지

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)':
game.cpp:108:6: warning: unused variable 'tm' [-Wunused-variable]
  108 |  int tm = (tl + tr) >> 1;
      |      ^~
game.cpp: In function 'll get(int)':
game.cpp:213:6: warning: unused variable 'tm' [-Wunused-variable]
  213 |  int tm = (tl + tr) >> 1;
      |      ^~

• Subtask 1: 10 / 10
• Subtask 2: 27 / 27
• Subtask 3: 26 / 26
• Subtask 4: 17 / 17
• Subtask 5: 0 / 20