제출 #276867

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
276867		_7_7_	게임 (IOI13_game)	C++14	63 / 100	3605 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 = 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);
}

컴파일 시 표준 에러 (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;
      |      ^~~

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