Submission #372156

---

Source Code Expand

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
using namespace std;
#define MOD @
#define ADD(X,Y) ((X) = ((X) + (Y)%MOD) % MOD)
typedef long long i64; typedef vector<int> ivec; typedef vector<string> svec;

struct segtree
{
	static const int DEPTH = 18;
	static const int SIZE = 1 << DEPTH;

	i64 sum[2 * SIZE]; int cnt[2 * SIZE];

	void init()
	{
		for (int i = 0; i < 2 * SIZE; ++i) {
			sum[i] = 0; cnt[i] = 0;
		}
	}

	void add(int p, int v)
	{
		sum[p + SIZE] += (i64)p * v;
		p += SIZE;
		cnt[p] += v;

		p >>= 1;
		while (p) {
			sum[p] = sum[p * 2] + sum[p * 2 + 1];
			cnt[p] = cnt[p * 2] + cnt[p * 2 + 1];
			p >>= 1;
		}
	}

	pair<i64, int> query(int L, int R)
	{
		i64 r1 = 0;
		int r2 = 0;

		L += SIZE; R += SIZE;
		while (L < R) {
			if (L & 1) {
				r1 += sum[L]; r2 += cnt[L];
				L++;
			}
			if (R & 1) {
				--R;
				r1 += sum[R]; r2 += cnt[R];
			}
			L >>= 1; R >>= 1;
		}
		return make_pair(r1, r2);
	}
};

const int OFS = 1000000000;
int N, Q;
set<int> locs[200100];
set<pair<int, int> > colors_gtr, colors_les;
segtree seg;

void flush_color(int a)
{
	if (locs[a].size() > 0) {
		int lg = *(--locs[a].end());
		int sm = *(locs[a].begin());

		colors_gtr.erase(make_pair(lg, a));
		colors_les.erase(make_pair(sm, a));
	}
}

void adjust_color(int a)
{
	if (locs[a].size() > 0) {
		int lg = *(--locs[a].end());
		int sm = *(locs[a].begin());

		colors_gtr.insert(make_pair(lg, a));
		colors_les.insert(make_pair(sm, a));
	}
}

void add_board(int x, int a)
{
	seg.add(a, 1);
	flush_color(a);
	locs[a].insert(x);
	adjust_color(a);
}

void erase_board(int x, int a)
{
	seg.add(a, -1);
	flush_color(a);
	locs[a].erase(x);
	adjust_color(a);
}

i64 solve(int target)
{
	if (target == -1) return 1LL << 62LL;

	auto gt = --colors_gtr.end();
	if (gt->second == target) --gt;

	auto le = colors_les.begin();
	if (le->second == target) ++le;

	int gtl = gt->first, lel = -le->first;
	i64 mv = (i64)min(gtl, lel) + gtl + lel;
	// printf("%d %d %d\n", target, gtl, lel);

	auto colorl = seg.query(0, target), colorg = seg.query(target, 200200);
	i64 ret = mv;
	ret += (i64)colorl.second * target - colorl.first;
	ret += colorg.first - (i64)colorg.second * target;

	return ret;
}

int med()
{
	int tot = (seg.query(0, 200200).second + 1) / 2;
	int left = 0, right = 200200;

	while (left < right) {
		int mid = (left + right) / 2;
		if (seg.query(0, mid + 1).second < tot) {
			left = mid + 1;
		} else {
			right = mid;
		}
	}

	return left;
}

int main()
{
	seg.init();
	colors_gtr.insert(make_pair(0, -1));
	colors_les.insert(make_pair(0, -1));

	scanf("%d", &N);
	for (int i = 0; i < N; ++i) {
		int x, a;
		scanf("%d%d", &x, &a);

		add_board(x, a);
	}
	scanf("%d", &Q);

	for (int i = 0; i < Q; ++i) {
		int c, y, b;
		scanf("%d%d%d", &c, &y, &b);
		if (c == 1) {
			add_board(y, b);
		} else {
			erase_board(y, b);
		}

		i64 ret = 1LL << 62LL;
		ret = min(ret, solve((--colors_gtr.end())->second));
		ret = min(ret, solve((colors_les.begin())->second));
		ret = min(ret, solve(med()));
		//printf("med: %d\n", med());

		printf("%lld\n", ret);
	}

	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:155:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
                 ^
./Main.cpp:158: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:162:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &Q);
                 ^
./Main.cpp:166: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