2019-2020 XX Open Cup Grand Prix of Korea 虚拟参赛 暨 补题

const int maxn = 510;

int n, m, ans = 0;
char str[maxn][maxn];

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++)
		scanf("%s", str[i] + 1);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			int ii = n - i + 1, jj = m - j + 1;
			int a = str[i][j] - '0', b = str[ii][jj] - '0';
			if (i == ii && j == jj) {
				if (a != 8) {
					ans = -1;
					break;
				}
			}
			else {
				if (a == 6) {
					if (b == 6)
						ans++;
					else if (b != 9) {
						ans = -1;
						break;
					}
				}
				else if (a == 9) {
					if (b == 9)
						ans++;
					else if (b != 6) {
						ans = -1;
						break;
					}
				}
				else if (a == 8) {
					if (b != 8) {
						ans = -1;
						break;
					}
				}
				else if (a == 7) {
					if (b != 7) {
						ans = -1;
						break;
					}
					else
						ans++;
				}
			}
		}
		if (ans == -1)
			break;
	}
	if (ans == -1)
		puts("-1");
	else
		printf("%d\n", ans/2);
	return 0;
}

const int maxn = 3e5+10;
const int P = 1e9+7;

int Plus(LL a, LL b) {
	return a + b >= P ? (a + b) % P : a + b;
}

int Mult(LL a, LL b) {
	return a * b >= P ? a * b % P : a * b;
}

struct SegmentTreeNode {
	int l, r, mid, pk, b;
} tree[maxn << 2];

int n, pw[maxn], G = 1, last_2[maxn], cnt = 0, gid[maxn];
LL pre[maxn];
vector<int> p2;

void Build(int v, int l, int r) {
	tree[v] = SegmentTreeNode{l, r, (l+r)>>1, 0, 0};
	if (l == r)
		return;
	else {
		Build(LCH(v), l, tree[v].mid);
		Build(RCH(v), tree[v].mid+1, tree[v].r);
	}
}

void Init() {
	pw[0] = 1;
	for (int i = 1; i <= n; i++)
		pw[i] = Mult(pw[i-1], 2);
	Build(1, 1, n);
}

void UpdateNode(int v, int pk, int b) {
	tree[v].b = Mult(pw[pk], tree[v].b);
	tree[v].b = Plus(tree[v].b, b);
	tree[v].pk += pk;
}

void Down(int v) {
	UpdateNode(LCH(v), tree[v].pk, tree[v].b);
	UpdateNode(RCH(v), tree[v].pk, tree[v].b);
	tree[v].pk = tree[v].b = 0;
}

void Update(int v, int l, int r, int pk, int b) {
	if (tree[v].l == l && tree[v].r == r)
		UpdateNode(v, pk, b);
	else {
		Down(v);
		if (l > tree[v].mid)
			Update(RCH(v), l, r, pk, b);
		else if (r <= tree[v].mid)
			Update(LCH(v), l, r, pk, b);
		else {
			Update(LCH(v), l, tree[v].mid, pk, b);
			Update(RCH(v), tree[v].mid+1, r, pk, b);
		}
	}
}

int Query(int v, int p, int x) {
	if (tree[v].l == tree[v].r)
		return Plus(Mult(pw[tree[v].pk], x), tree[v].b);
	Down(v);
	if (p > tree[v].mid)
		return Query(RCH(v), p, x);
	else
		return Query(LCH(v), p, x);
}

int main() {
	scanf("%d", &n);
	Init();
	pre[1] = 0;
	last_2[1] = -1;
	for (int i = 1; i <= n; i++) {
		int op;
		scanf("%d", &op);
		if (op == 1){
			int k;
			scanf("%d", &k);
			if (k) {
				Update(1, 1, G++, 0, k);
				pre[G] = pre[G-1] + k;
				last_2[G] = 0;
			}
			else {
				Update(1, 1, G++, 1, 0);
				Update(1, G, G, 1, 1);
				pre[G] = 0;
				last_2[G] = last_2[G-1] ? last_2[G-1] : G;
				gid[G] = cnt++;
				p2.push_back(G);
			}
		}
		else if (op == 2){
			int g, x;
			scanf("%d%d", &g, &x);
			printf("%d\n", Query(1, g+1, x-1));
		}
		//下面写的和狗屎一样丑, 能力有限, 见谅
		else {
			int x;
			scanf("%d", &x);
			int cur = G, res = 1, L = 2, R = G, flag = 1;
			for (int i = p2.size() - 1; ~i; i--) {
				// 等于0也可回溯上一步
				if (x - pre[cur] >= 0) {
					x -= pre[cur];
					if (x & 1) {
						res = p2[i];
						flag = 0;
						break;
					}
					else {
						if (x == 0) {
							cur = last_2[p2[i]];
							i = gid[cur];
						}
						x >>= 1;
						cur = p2[i] - 1;
						R = cur;
					}
				}
				else {
					L = p2[i] + 1, R = cur;
					break;
				}
			}
			if (flag) {
				while (L <= R) {
					int mid = (L + R) >> 1;
					if (x - (pre[cur] - pre[mid-1]) < 0) {
						L = mid + 1;
						res = mid;
					}
					else
						R = mid - 1;
				}
			}
			printf("%d\n", res-1);
		}
	}
	return 0;
}

const int maxn = 1e5+10;
const int maxm = 3e5+10;

int n, m, s, t, vis[maxn];
vector<int> G[maxm], G2[maxm], ans;

struct Edge {
	int u, v, c, flag;
} edges[maxm];

bool cmp( int i, int j) {
	return edges[i].c < edges[j].c;
}

void dfs(int v) {
	vis[v] = 1;
	for (auto i : G2[v]) {
		Edge &e = edges[i];
		e.flag = 1;
		if (!vis[e.u])
			dfs(e.u);
	}
}

bool dfs2(int u) {
	if (u == t)
		return true;
	vis[u] = 2;
	Edge &e = edges[G[u][0]];
	if (vis[e.v] == 2)
		return false;
	ans.push_back(e.c);
	return dfs2(e.v);
}

void Print() {
	for (auto x : ans)
		printf("%d ", x);
	puts("");
}

int main() {
	scanf("%d%d%d%d", &n, &m, &s, &t);
	for (int i = 1; i <= m; i++) {
		int u, v, c;
		scanf("%d%d%d", &u, &v, &c);
		edges[i] = Edge{u, v, c, 0};
		G2[v].push_back(i);
	}
	dfs(t);
	for (int i = 1; i <= m; i++) {
		Edge &e = edges[i];
		if (e.flag) {
			G[e.u].push_back(i);
		}
	}
	if (!G[s].size())
		puts("IMPOSSIBLE");
	else {
		for (int i = 1; i <= n; i++)
			sort(G[i].begin(), G[i].end(), cmp);
		if (dfs2(s))
			Print();
		else
			puts("TOO LONG");
	}
	return 0;
}

const int maxn = 2.5e5 + 10;

int n, a[maxn], b[maxn];
LL ans;
vector<int> sa, sb;

LL sol() {
	LL res = 0;
	sa.clear();
	sb.clear();
	for (int i = 1; i <= n; i++) {
		if (a[i])
			sa.push_back(i);
		if (b[i])
			sb.push_back(i);
	}
	for (int i = 0; i < sa.size(); i++)
		res += llabs(sa[i] - sb[i]);
	return res;
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
		scanf("%d", a + i);
	for (int i = 1; i <= n; i++)
		scanf("%d", b + i);
	if ((n&1) == 0) {
		for (int i = 1; i <= n; i++) {
			a[i] = (a[i] > n/2);
			b[i] = (b[i] <= n/2);
		}
		ans = sol();
	}
	else {
		int pa = -1, pb = -1;
		for (int i = 1; i <= n; i++) {
			if (a[i] == n/2 + 1)
				pa = i;
			if (b[i] == n/2 + 1)
				pb = i;
			a[i] = a[i] > n/2 + 1;
			b[i] = b[i] <= n/2;
		}
		a[pa] = 1, b[pb] = 1;
		ans = sol();
		a[pa] = 0, b[pb] = 0;
		ans = min(ans, sol());
	}
	printf("%lld\n", ans);
	return 0;
}

const int maxn = 2.5e5+10;

struct Segment {
	int l, r, w;
	bool operator < (const Segment &S) const {
		return l == S.l ? r > S.r : l < S.l;
	}
} segments[maxn];

int n;

vector<int> son[maxn];
vector<int> stk;

void Build() {
	stk.push_back(0);
	for (int i = 1; i <= n; i++) {
		Segment &s = segments[i];
		int fa = stk.back();
		while (!(segments[fa].l <= s.l && s.r <= segments[fa].r)) {
			stk.pop_back();
			fa = stk.back();
		}
		son[fa].push_back(i);
		stk.push_back(i);
	}
#ifdef D
	printf("Tree:\n");
	for (int i = 0; i <= n; i++) {
		printf("%d:\n", i);
		for (auto v : son[i])
			printf("%d ", v);
		puts("");
	}
#endif
}

MaxHeap heap[maxn];
int idx = 0;

// 启发式合并
int Merge(int x, int y) {
	vector<LL> pool;
	if (heap[x].size() > heap[y].size())
		swap(x, y);
	while (!heap[x].empty()) {
		pool.push_back(heap[x].top() + heap[y].top());
		heap[x].pop(), heap[y].pop();
	}
	for (auto t : pool)
		heap[y].push(t);
	return y;
}

// 返回的是当前点的堆(的下标)
int dfs(int u) {
	if (!son[u].size()) {
		heap[++idx].push(segments[u].w);
		return idx;
	}
	int cur = dfs(son[u][0]);
	for (int i = 1; i < son[u].size(); i++) {
		int p = dfs(son[u][i]);
		cur = Merge(cur, p);
	}
	heap[cur].push(segments[u].w);
	return cur;
}

int main() {
	scanf("%d", &n);
	segments[0] = Segment{1, 1000000, 0};
	for (int i = 1; i <= n; i++) {
		int l, r, w;
		scanf("%d%d%d", &l, &r, &w);
		segments[i] = Segment{l, r, w};
	}
	sort(segments, segments + n + 1);
	Build();
	int p = dfs(0);
	LL ans = 0;
	for (int i = 1; i <= n; i++) {
		if (!heap[p].empty()) {
			ans += heap[p].top();
			heap[p].pop();
		}
		printf("%lld ", ans);
	}
	return 0;
}

typedef pair<int, LL> PIL;
typedef pair<LL, int> PLI;

const int maxn = 2.5e5+10;

struct HeapTwo {
	PLI val[2];
	void Reset() {
		val[0] = val[1] = make_pair(INF, -1);
	}
	void Push(PLI x) {
		if (x < val[0])
			val[1] = val[0], val[0] = x;
		else if (x < val[1])
			val[1] = x;
	}
	LL Top(int u) {
		return val[u == val[0].second].first;
	}
} heap[maxn];

int n, size[maxn], vis[maxn];
vector<PIL> T[2][maxn], descendant, anscentant[maxn];

LL ans[maxn];

// 维护size用来点分, 同时记录点到根的距离.
void dfs(int k, int u, int f, LL dis) {
	size[u] = 1;
	descendant.emplace_back(u, dis);
	for (auto e : T[k][u]) {
		int v = e.first;
		LL w = e.second;
		if (v != f && !vis[v]) {
			dfs(k, v, u, dis + w);
			size[u] += size[v];
		}
	}
}

int Center(int k, int u) {
	// 每一次求重心的时候, 要重新求子代, 注意清空
	descendant.clear();
	dfs(k, u, 0, 0);
	int tot_size = descendant.size();
	for (auto des : descendant) {
		int is_center = 1;
		int x = des.first;
		for (auto e : T[k][x]) {
			int v = e.first;
			if (vis[v])
				continue;
			// size[x] > size[v] == v 是 x 的儿子
			if (size[x] > size[v] && (size[v] << 1) > tot_size) {
				is_center = 0;
				break;
			}
			// size[x] < size[v] == v 是 x 的父亲
			if (size[x] < size[v] && ((tot_size - size[x]) << 1) > tot_size) {
				is_center = 0;
				break;
			}
		}
		if (is_center) {
			// 找到重心, 需要以重心为根, 求一下子代到根(这个祖先)的距离
			descendant.clear();
			dfs(k, x, 0, 0);
			return x;
		}
	}
	return -1;
}

void Decomp0(int k, int u) {
	int c = Center(k, u);
	for (auto des : descendant)
		// c 为所有子代的一个祖先
		anscentant[des.first].emplace_back(c, des.second);
	// 删除c, 做剩下的森林
	vis[c] = 1;
	for (auto e : T[k][c]) {
		int v = e.first;
		if (!vis[v])
			Decomp0(k, v);
	}
	// 深搜, 可回溯, 节省空间(虽然不是很必要)
	vis[c] = 0;
}

void Decomp1(int k, int u) {
	int c = Center(k, u);
	// 先初始化堆
	for (auto des : descendant) {
		int v = des.first;
		for (auto ansc : anscentant[v]) {
			int a1 = ansc.first;
			heap[a1].Reset();
		}
	}
	// 对所有(L1, L2), 把所有 dist(T1, c, v) + dist(T2, a, v) 压入堆
	// 得到每个(L1, L2)的最小值和次小值
	for (auto des : descendant) {
		int v = des.first;
		LL dis2 = des.second;
		for (auto ansc : anscentant[v]) {
			int a1 = ansc.first;
			LL dis1 = ansc.second;
			heap[a1].Push(make_pair(dis1 + dis2, v));
		}
	}
	// 更新答案
	for (auto des : descendant) {
		int v = des.first;
		LL dis1 = des.second;
		for (auto ansc : anscentant[v]) {
			int a1 = ansc.first;
			LL dis2 = ansc.second;
			ans[v] = min(ans[v], dis1 + dis2 + heap[a1].Top(v));
		}
	}
	// 继续点分
	vis[c] = 1;
	for (auto e : T[k][c]) {
		int v = e.first;
		if (!vis[v])
			Decomp1(k, v);
	}
	vis[c] = 0;
}

int main() {
	scanf("%d", &n);
	for (int k = 0; k < 2; k++)
		for (int i = 1; i < n; i++) {
			int u, v;
			LL w;
			scanf("%d%d%lld", &u, &v, &w);
			T[k][u].emplace_back(v, w);
			T[k][v].emplace_back(u, w);
		}
	Decomp0(0, 1);
	for (int i = 1; i <= n; i++)
		ans[i] = INF;
	Decomp1(1, 1);
	for (int i = 1; i <= n; i++)
		printf("%lld\n", ans[i]);
	return 0;
}