Submission #205123

#	Time	Username	Problem	Language	Result	Execution time	Memory
205123		ics0503	Minerals (JOI19_minerals)	C++17	90 / 100	67 ms	17908 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;
	if (s == e) return;
	int m = (s + e) / 2, l = seg[now].l, r = seg[now].r, bef;
	for (int i = m + 1; i <= e; i++) {
		is_in[i] = !is_in[i];
		bef = Query(L[i]);
	}
	for (int p : seg[now].L) {
		if (seg[r].L.size() == (e-(m+1)+1)) { seg[l].L.push_back(p); continue; }
		if (seg[l].L.size() == (m-s+1)) { seg[r].L.push_back(p); continue; }
		int res = Query(p);
		if (res == bef) {
			if (is_in[s])seg[l].L.push_back(p);
			else seg[r].L.push_back(p);
		}
		else {
			if (is_in[s])seg[r].L.push_back(p);
			else seg[l].L.push_back(p);
		}
		bef = res;
	}
	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);
		cnt = res;
	}
	for (int i = 0; i < n; i++)is_in[i] = 1;
	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;
		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:33:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (seg[r].L.size() == (e-(m+1)+1)) { seg[l].L.push_back(p); continue; }
       ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
minerals.cpp:34:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (seg[l].L.size() == (m-s+1)) { seg[r].L.push_back(p); continue; }
       ~~~~~~~~~~~~~~~~^~~~~~~~~~
minerals.cpp:36: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: 30 / 30
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 5 / 5
• Subtask 8: 5 / 5
• Subtask 9: 0 / 10