제출 #366371

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

game

#include <game.h>
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int R, C;
struct dty {
	vector<int> L, R, K;
	vector<ll> st;
    dty() : L(2, 0), R(2, 0), K(2, -1), st(2, 0) {}
	inline int new_node() {
		L.emplace_back(0);
		R.emplace_back(0);
		K.emplace_back(-1);
		st.emplace_back(0);
		return L.size()-1;
	}
	inline void upd(int i, int s, int e, int y, ll v) {
		if (s==e) { st[i]=v; return ; }
		int m=(s+e)/2;
		if (K.size()==2&&K[i]==-1) {
			K[i]=y;
			st[i]=v;
			return ;
		}
		if (K[i]!=-1) {
			if (K[i]==y) { st[i]=v; return ; }
			if (K[i]<=m) { L[i]=new_node(); K[L[i]]=K[i]; st[L[i]]=st[i]; }
			else { R[i]=new_node(); K[R[i]]=K[i]; st[R[i]]=st[i]; }
			K[i]=-1;
		}
		if (y<=m) {
			if (!L[i]) L[i]=new_node();
			upd(L[i], s, m, y, v);
		}
		else {
			if (!R[i]) R[i]=new_node();
			upd(R[i], m+1, e, y, v);
		}
		st[i]=__gcd(st[L[i]], st[R[i]]);
	}
	inline ll get(int i, int s, int e, int l, int r) {
		if (!i||e<l||r<s) return 0;
		if (K[i]!=-1) return (l<=K[i]&&K[i]<=r)?st[i]:0;
		int m=(s+e)/2;
		if (l<=s&&e<=r) return st[i];
		return __gcd(get(L[i], s, m, l, r), get(R[i], m+1, e, l, r));
	}
};

struct dtx {
    vector<dty> seg;
	vector<int> L, R;
    dtx() : L(2, 0), R(2, 0), seg(2, dty()) {}
	inline int new_node() {
		L.emplace_back(0);
		R.emplace_back(0);
		seg.emplace_back(dty());
		return L.size()-1;
	}
	inline void upd(int i, int s, int e, int x, int y, ll v) {
		if (s==e) {
			seg[i].upd(1, 0, C-1, y, v);
			return ;
		}
		int m=(s+e)/2;
		if (x<=m) {
			if (!L[i]) L[i]=new_node();
			upd(L[i], s, m, x, y, v);
		}
		else {
			if (!R[i]) R[i]=new_node();
			upd(R[i], m+1, e, x, y, v);
		}
		seg[i].upd(1, 0, C-1, y,
			__gcd(seg[L[i]].get(1, 0, C-1, y, y), seg[R[i]].get(1, 0, C-1, y, y)));
	}
	inline ll get(int i, int s, int e, int l, int r, int d, int u) {
		if (!i||e<l||r<s) return 0;
		if (l<=s&&e<=r) return seg[i].get(1, 0, C-1, d, u);
		int m=(s+e)/2;
		return __gcd(get(L[i], s, m, l, r, d, u), get(R[i], m+1, e, l, r, d, u));
	}
}S;

void init(int R, int C) {
	::R=R;
	::C=C;
}

void update(int P, int Q, ll K) {
	S.upd(1, 0, R-1, P, Q, K);
}

ll calculate(int P, int Q, int U, int V) {
	return S.get(1, 0, R-1, P, U, Q, V);
}

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

game.cpp: In constructor 'dtx::dtx()':
game.cpp:54:17: warning: 'dtx::R' will be initialized after [-Wreorder]
   54 |  vector<int> L, R;
      |                 ^
game.cpp:53:17: warning:   'std::vector<dty> dtx::seg' [-Wreorder]
   53 |     vector<dty> seg;
      |                 ^~~
game.cpp:55:5: warning:   when initialized here [-Wreorder]
   55 |     dtx() : L(2, 0), R(2, 0), seg(2, dty()) {}
      |     ^~~

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