Submission #366361

#	Time	Username	Problem	Language	Result	Execution time	Memory
366361		dennisstar	Game (IOI13_game)	C++17	0 / 100	200 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) {}
	int new_node() {
		L.emplace_back(0);
		R.emplace_back(0);
		K.emplace_back(-1);
		st.emplace_back(0);
		return L.size()-1;
	}
	void upd(int i, int s, int e, int y, ll v) {
		int m=(s+e)/2;
		if (K.size()==2&&!K[i]) {
			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]]);
	}
	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()) {}
	int new_node() {
		L.emplace_back(0);
		R.emplace_back(0);
		seg.emplace_back(dty());
		return L.size()-1;
	}
	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]].st[1], seg[R[i]].st[1]));
	}
	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);
}

Compilation message (stderr)

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

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