Submission #376369

---

Source Code Expand

#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#include <cassert>
#include <limits>
#include <functional>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#if defined(_MSC_VER) || __cplusplus > 199711L
#define aut(r,v) auto r = (v)
#else
#define aut(r,v) __typeof(v) r = (v)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
using namespace std;
typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pair<int,int> > vpii; typedef long long ll;
template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }

template<typename It>
void make_fenwick(It beg, size_t n) {
	for(size_t i = 0; i < n; i ++) {
		size_t p = i | (i+1);
		if(p < n) beg[p] += beg[i];
	}
}
template<typename It, typename Val>
void add_fenwick(It beg, size_t n, size_t i, Val val) {
	for(; i < n; i |= i+1) beg[i] += val;
}
template<typename It, typename Val>
Val sum_fenwick(It beg, size_t i, Val sum) {
	for(; i > 0; i = i & (i-1)) sum += beg[i-1];
	return sum;
}
template<typename It>
typename std::iterator_traits<It>::value_type sum_fenwick(It beg, size_t i) {
	return sum_fenwick(beg, i, typename std::iterator_traits<It>::value_type());
}

size_t highestOneBit(size_t v) {
	v |= v >> 1;
	v |= v >> 2;
	v |= v >> 4;
	v |= v >> 8;
	v |= v >> 16;
#if SIZE_MAX > 0xffffffffULL
	v |= v >> 32;
#endif
	return (v >> 1) + 1;
}

template<typename It, typename Val, typename Cmp>
size_t search_fenwick(It beg, size_t n, Val val, Val left, Cmp cmp) {
	if(!cmp(left, val)) return 0;
	size_t i = 0;
	for(size_t w = highestOneBit(n); w > 0; w >>= 1) {
		if(i + w <= n) {
			Val mid = left;
			mid += beg[i + w - 1];
			if(cmp(mid, val)) {
				i += w;
				left = mid;
			}
		}
	}
	return i + 1;
}
template<typename It, typename Val>
size_t select_fenwick(It beg, size_t n, Val k) {
	return search_fenwick(beg, n, k + 1, Val(), std::less<Val>()) - 1;
}

struct DynamicRunLength {
	int n, numRuns;
	vector<int> ft;
	vector<int> colors;
	vector<bool> runs;	//runの左端を保持する
	vector<int> ftRuns;

	void init(int X) {
		n = 0, numRuns = 0;
		ft.assign(X, 0);
		colors.assign(X, -1);
		runs.assign(X, false);
		ftRuns.assign(X, 0);
	}

	//ft, colorsに事前にデータを格納しておいてからbuildを呼ぶことで構築することができる
	void build() {
		int X = ft.size();
		assert(colors.size() == X);
		runs.assign(X, false);
		ftRuns.assign(X, 0);
		n = 0, numRuns = 0;

		int prevColor = -1;
		for(int i = 0; i < X; ++ i) {
			assert(ft[i] == 0 || ft[i] == 1);
			assert((ft[i] == 1) == (colors[i] != -1));

			if(ft[i] == 1) {
				++ n;
				int a = colors[i];
				if(a != prevColor) {
					++ numRuns;
					runs[i] = true;
					ftRuns[i] = 1;
					prevColor = a;
				}
			}
		}
		make_fenwick(ft.begin(), ft.size());
		make_fenwick(ftRuns.begin(), ftRuns.size());
	}

	void insert(int x, int a) {
		assert(0 <= x && x < (int)ft.size());
		assert(colors[x] == -1);

		int rank = sum_fenwick(ft.begin(), x);
		if(rank != n) {
			int nextPos = select_fenwick(ft.begin(), ft.size(), rank);
			if(colors[nextPos] == a && runs[nextPos]) {
				-- numRuns;
				runs[nextPos] = false;
				add_fenwick(ftRuns.begin(), ftRuns.size(), nextPos, -1);
			}else if(colors[nextPos] != a && !runs[nextPos]) {
				++ numRuns;
				runs[nextPos] = true;
				add_fenwick(ftRuns.begin(), ftRuns.size(), nextPos, +1);
			}
		}
		bool newRun = true;
		if(rank != 0) {
			int prevPos = select_fenwick(ft.begin(), ft.size(), rank - 1);
			if(colors[prevPos] == a)
				newRun = false;
		}
		if(newRun) {
			++ numRuns;
			runs[x] = true;
			add_fenwick(ftRuns.begin(), ftRuns.size(), x, +1);
		}

		add_fenwick(ft.begin(), ft.size(), x, +1);
		colors[x] = a;
		++ n;
	}

	void erase(int x) {
		assert(0 <= x && x < (int)ft.size());
		assert(colors[x] != -1);
		int a = colors[x];

		if(runs[x]) {
			-- numRuns;
			runs[x] = false;
			add_fenwick(ftRuns.begin(), ftRuns.size(), x, -1);

			int rank = sum_fenwick(ft.begin(), x);
			if(rank != n - 1) {
				int nextPos = select_fenwick(ft.begin(), ft.size(), rank + 1);
				if(colors[nextPos] == a) {
					assert(!runs[nextPos]);
					++ numRuns;
					runs[nextPos] = true;
					add_fenwick(ftRuns.begin(), ftRuns.size(), nextPos, +1);
				}else {
					assert(runs[nextPos]);
					if(rank != 0) {
						int prevPos = select_fenwick(ft.begin(), ft.size(), rank - 1);
						if(colors[prevPos] == colors[nextPos]) {
							-- numRuns;
							runs[nextPos] = false;
							add_fenwick(ftRuns.begin(), ftRuns.size(), nextPos, -1);
						}
					}
				}
			}
		}

		add_fenwick(ft.begin(), ft.size(), x, -1);
		colors[x] = -1;
		-- n;
	}

	//左端から(k+1)番目のrunの左端を返す
	int selectRunLeft(int k) const {
		if(k >= numRuns) return INF;
		return select_fenwick(ftRuns.begin(), ftRuns.size(), k);
	}

	//右端から(k+1)番目のrunの右端を返す
	int selectRunRight(int k) const {
		if(k >= numRuns) return INF;
		if(k == 0)
			return select_fenwick(ft.begin(), ft.size(), n - 1);
		int i = select_fenwick(ftRuns.begin(), ftRuns.size(), numRuns - k);
		int rank = sum_fenwick(ft.begin(), i);
		return select_fenwick(ft.begin(), ft.size(), rank - 1);
	}
};

struct Query {
	int ty, x, a;
};

int main() {
	int N;
	scanf("%d", &N);
	vector<Query> queries;
	rep(i, N) {
		int x, a;
		scanf("%d%d", &x, &a);
		queries.push_back({ 0, x, a });
	}
	int Q;
	scanf("%d", &Q);
	set<pii> signs;
	rep(i, Q) {
		int c, y, b;
		scanf("%d%d%d", &c, &y, &b);
		queries.push_back({ c, y, b });
	}
	vector<int> xs(N + Q);
	rep(i, N + Q)
		xs[i] = queries[i].x;
	sort(all(xs));
	xs.erase(unique(all(xs)), xs.end());
	int X = xs.size();
	const int C = 200001;
	int totalCnt = 0;
	long long totalSum = 0;
	vector<int> cnt(C, 0);
	vector<int> ftCnt(C, 0);
	vector<long long> ftSum(C, 0);
	DynamicRunLength runs;
	runs.init(X);
	signs.clear();
	rep(i, N) {
		const Query &q = queries[i];
		++ totalCnt;
		totalSum += q.a;
		++ cnt[q.a];
		++ ftCnt[q.a];
		ftSum[q.a] += q.a;
		int xi = lower_bound(all(xs), q.x) - xs.begin();
		++ runs.ft[xi];
		runs.colors[xi] = q.a;
	}
	make_fenwick(ftCnt.begin(), ftCnt.size());
	make_fenwick(ftSum.begin(), ftSum.size());
	runs.build();
	rep(i, Q) {
		const Query &q = queries[N + i];
		if(q.ty == 1) {
			signs.insert(mp(q.x, q.a));
			++ totalCnt;
			totalSum += q.a;
			++ cnt[q.a];
			add_fenwick(ftCnt.begin(), ftCnt.size(), q.a, +1);
			add_fenwick(ftSum.begin(), ftSum.size(), q.a, +q.a);
			int xi = lower_bound(all(xs), q.x) - xs.begin();
			runs.insert(xi, q.a);
		}else if(q.ty == 2) {
			signs.erase(mp(q.x, q.a));
			-- totalCnt;
			totalSum -= q.a;
			-- cnt[q.a];
			add_fenwick(ftCnt.begin(), ftCnt.size(), q.a, -1);
			add_fenwick(ftSum.begin(), ftSum.size(), q.a, -q.a);
			int xi = lower_bound(all(xs), q.x) - xs.begin();
			runs.erase(xi);
		}

		int leftPos = runs.selectRunLeft(0);
		int leftColor = runs.colors[leftPos];

		int rightPos = runs.selectRunRight(0);
		int rightColor = runs.colors[rightPos];

		int medianColor = select_fenwick(ftCnt.begin(), ftCnt.size(), (totalCnt - 1) / 2);

		int candidateColors[3] = { leftColor, rightColor, medianColor };
		sort(candidateColors, candidateColors + 3);
		int K = unique(candidateColors, candidateColors + 3) - candidateColors;

		long long ans = INFL;
		rep(k, K) {
			int color = candidateColors[k];

			if(cnt[color] == totalCnt) {
				ans = 0;
				break;
			}

			int left, right;

			if(color != leftColor)
				left = xs[leftPos];
			else
				left = xs[runs.selectRunLeft(1)];

			if(color != rightColor)
				right = xs[rightPos];
			else
				right = xs[runs.selectRunRight(1)];

			if(0 < left) left = 0;
			if(right < 0) right = 0;

			int cntL = sum_fenwick(ftCnt.begin(), color);
			long long sumL = sum_fenwick(ftSum.begin(), color);
			int cntR = totalCnt - cntL;
			long long sumR = totalSum - sumL;

			long long totalTime = 0;

			totalTime += (long long)min(-left, right) + (right - left);

			totalTime += (long long)color * cntL - sumL;
			totalTime += sumR - (long long)color * cntR;

			amin(ans, totalTime);
		}

		printf("%lld\n", ans);
	}
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:229:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
                 ^
./Main.cpp:233:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &x, &a);
                        ^
./Main.cpp:237:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &Q);
                 ^
./Main.cpp:241:30: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &c, &y, &b);
                              ^

Judge Result