Submission #204989

#	Time	Username	Problem	Language	Result	Execution time	Memory
204989		ics0503	Minerals (JOI19_minerals)	C++17	40 / 100	48 ms	14504 KiB

minerals

#include "minerals.h"
#include<vector>
using namespace std;
vector<int>L, R;
struct SEG {
	vector<int>L;
	int l, r, s, e, who, ck;
} seg[212121];
int segN = 1, segW[212121];
void make_seg(int now, int s, int e) {
	seg[now].who = s;
	seg[now].s = s; seg[now].e = e;
	if (s == e) {
		segW[s] = now;
		return;
	}
	int m = (s + e) / 2;
	if (!seg[now].l)seg[now].l = ++segN;
	make_seg(seg[now].l, s, m);
	if (!seg[now].r)seg[now].r = ++segN;
	make_seg(seg[now].r, m + 1, e);
}
int is_in[212121];
void go_down(int now, int s, int e) {
	seg[now].ck = 1;
//	printf("%d %d %d\n", now, s, e);
	if (s == e || seg[now].L.empty()) {
		for (int p : seg[now].L) if (is_in[p])Query(p);
		Query(L[s]);
		return;
	}
	int m = (s + e) / 2, l = seg[now].l, r = seg[now].r, bef;
	for (int i = m + 1; i <= e; i++)bef = Query(L[i]);
	for (int p : seg[now].L) {
		int res = Query(p);
		is_in[p] = !is_in[p];
		if (res == bef) {
			seg[l].L.push_back(p);
			Query(p);
			is_in[p] = !is_in[p];
		}
		else {
			seg[r].L.push_back(p);
			Query(p);
			is_in[p] = !is_in[p];
		}
	}
	go_down(l, s, m);
}
void Solve(int n) {
	int cnt = 0;
	for (int i = 1; i <= n * 2; i++) {
		int res = Query(i);
		if (res != cnt) {
			L.push_back(i);
		} else {
			seg[1].L.push_back(i);
			Query(i);
		}
		cnt = res;
	}
	make_seg(1, 0, n - 1);
	go_down(1, 0, n - 1);
	for (int i = 2; i <= segN; i++) {
		int s = seg[i].s, e = seg[i].e;
		if (seg[i].ck || seg[i].L.empty() || s == e)continue;
		for(int j = s; j <= e; j++) Query(L[j]);
		go_down(i, s, e);
	}
	for (int i = 0; i < n; i++) {
		for (int p : seg[segW[i]].L) {
			Answer(L[i], p);
		}
	}
}

Compilation message (stderr)

minerals.cpp: In function 'void go_down(int, int, int)':
minerals.cpp:37:3: warning: 'bef' may be used uninitialized in this function [-Wmaybe-uninitialized]
   if (res == bef) {
   ^~

• Subtask 1: 6 / 6
• Subtask 2: 25 / 25
• Subtask 3: 9 / 9
• Subtask 4: 0 / 30
• Subtask 5: 0 / 5
• Subtask 6: 0 / 5
• Subtask 7: 0 / 5
• Subtask 8: 0 / 5
• Subtask 9: 0 / 10