Submission #373124

---

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; }

typedef int Val;
typedef long long Sum;
struct Node {
	int priority;
	Node *ch[2];
	//ここに欲しい情報(値のsum, 値のmin, etc.)
	//splitのためにデフォルトでsizeがある
	Val val; int size;
	Sum sum;
	//情報の初期値を設定する
	Node(Val v, int p)
		: priority(p)
		, val(v), size(1), sum(v) { ch[0] = ch[1] = NULL; }
};
//NULL用に関数を作っておくと便利(Nodeのコンストラクタと同じく初期値に注意)
//addをvalやminiにも足している点に注意。こんなふうにできないと遅延評価はできない
Val val(Node *x) { assert(x); return x->val; }
Sum sum(Node *x) { return !x ? 0 : x->sum; }
int size(Node *x) { return !x ? 0 : x->size; }

Node *update(Node *x) {
	//ここで情報の更新を行う
	if(!x) return x;
	x->size = size(x->ch[0]) + 1 + size(x->ch[1]);
	x->sum = sum(x->ch[0]) + x->val + sum(x->ch[1]);
	return x;
}

Node *link(Node *x, Node *c, bool b) {
	x->ch[b] = c; return update(x);
}
Node *merge(Node *x, Node *y) {
	x = update(x); y = update(y);
	if(!x || !y) return x ? x : y;
	if(x->priority < y->priority) {
		return link(x, merge(x->ch[1], y), 1);
	}else {
		return link(y, merge(x, y->ch[0]), 0);
	}
}
//サイズによってsplitする。　([0,k) , [k,n))
typedef pair<Node*, Node*> NPair;
NPair split(Node *t, int k) {
	if(!update(t)) return mp((Node*)NULL, (Node*)NULL);
	if(size(t->ch[0]) < k) {
		NPair u = split(t->ch[1], k - size(t->ch[0]) - 1);
		return mp(link(t, u.first, 1), u.second);
	}else {
		NPair u = split(t->ch[0], k);
		return mp(u.first, link(t, u.second, 0));
	}
}
Node *singleton(Val val) { return update(new Node(val, rand())); }

//ソート済みの列に対するlowerbound
int lowerbound(Node *t, Val x) {
	if(!update(t)) return 0;
	if(x <= val(t)) {
		return lowerbound(t->ch[0], x);
	}else {
		return size(t->ch[0]) + 1 + lowerbound(t->ch[1], x);
	}
}

//ソート済みの列に対するinsert
Node *insert(Node *t, Val x) {
	int k = lowerbound(t, x);
	NPair p = split(t, k);
	return merge(p.first, merge(singleton(x), p.second));
}

//ソート済みの列に対するerase
Node *erase(Node *t, Val x) {
	int k = lowerbound(t, x);
	NPair p = split(t, k);
	NPair q = split(p.second, 1);
	assert(val(q.first) == x);	//存在しない時にどうするかは場合によって書き換えること
	delete q.first;
	return merge(p.first, q.second);
}

struct DynamicRMQ {
	typedef int Val;
	int n;
	vector<Val> d;
	void init(int nmin) {
		for(n = 1; n < nmin; n *= 2);
		d.assign(n * 2, -INF);
	}
	void update(int i, Val x) {
		d[n+i] = x;
		for(int k = (n+i)/2; k > 0; k >>= 1) 
			d[k] = max(d[k * 2], d[k * 2 + 1]);
	}
	Val get(int i) const { return d[n+i]; }
	//[l, r)
	Val query(int l, int r) const {
		Val m = -INF;
		for(; l && l + (l&-l) <= r; l += l&-l)
			m = max(m, d[(n+l) / (l&-l)]);
		for(; l < r; r -= r&-r)
			m = max(m, d[(n+r) / (r&-r) - 1]);
		return m;
	}
};

long long solve(ll left, ll right) {
	assert(left <= right);
	if(0 <= left)
		return right;
	else if(right <= 0)
		return -left;
	else
		return min(-left, right) + (right - left);
}

int main() {
	int N;
	scanf("%d", &N);
	set<pii> signs;
	Node *t = NULL;
	const int C = 200001;
	vector<set<int> > poses(C);
	DynamicRMQ rmqMin, rmqMax;
	rmqMin.init(C);
	rmqMax.init(C);
	rep(i, N) {
		int x, a;
		scanf("%d%d", &x, &a);
		signs.insert(mp(x, a));
		poses[a].insert(x);
		rmqMin.update(a, -*poses[a].begin());
		rmqMax.update(a, *poses[a].rbegin());
		t = insert(t, a);
	}
	int Q;
	scanf("%d", &Q);
	rep(ii, Q) {
		{	int c, y, b;
			scanf("%d%d%d", &c, &y, &b);
			/*while(1) {
				if(signs.empty()||rand()%2==0){
					c = 1, y = rand() % 2000 - 1000, b = rand() % 10;
					auto it = signs.lower_bound(mp(y,0));
					if(it != signs.end() && it->first == y) continue;
				}else{
					c = 2;
					int k = rand() % signs.size();
					auto it = signs.begin();
					rep(j, k) ++ it;
					y = it->first, b = it->second;
				}
				break;
			}*/
			if(c == 1) {
				signs.insert(mp(y, b));
				poses[b].insert(y);
				rmqMin.update(b, -*poses[b].begin());
				rmqMax.update(b, *poses[b].rbegin());
				t = insert(t, b);
			}else if(c == 2) {
				signs.erase(mp(y, b));
				poses[b].erase(y);
				rmqMin.update(b, poses[b].empty() ? -INF : -*poses[b].begin());
				rmqMax.update(b, poses[b].empty() ? -INF : *poses[b].rbegin());
				t = erase(t, b);
			}
		}
		long long ans = INFL;
		if((int)signs.size() <= 1) {
			puts("0");
			continue;
		}
		int left = signs.begin()->first;
		int leftcol = signs.begin()->second;
		int right = signs.rbegin()->first;
		int rightcol = signs.rbegin()->second;

		{	//leftcol,rightcol以外ので塗り替える場合

			int num = size(t);
			NPair p = split(t, (num-1) / 2);
			NPair q = split(p.second, 1);
			assert(q.first != 0);
			int med = val(q.first);
			long long timeSum = 0;
			timeSum += (ll)med * size(p.first) - sum(p.first);
			timeSum += sum(q.second) - (ll)med * size(q.second);
			t = merge(p.first, merge(q.first, q.second));

			amin(ans, timeSum + solve(left, right));
		}

		
		rep(lr, 2) {
			//colで塗り替える場合
			int col = lr == 0 ? leftcol : rightcol;
			int left2 = min(-rmqMin.query(0, col), -rmqMin.query(col+1, C));
			int right2 = max(rmqMax.query(0, col), rmqMax.query(col+1, C));

			assert((left2 == INF) == (right2 == -INF));
			if(left2 == INF) {
				amin(ans, 0);
				break;
			}

			int k = lowerbound(t, col);
			NPair p = split(t, k);
			long long timeSum = 0;
			timeSum += (ll)col * size(p.first) - sum(p.first);
			timeSum += sum(p.second) - (ll)col * size(p.second);
			t = merge(p.first, p.second);

			amin(ans, timeSum + solve(left2, right2));
		}

		/*ll naiveans = INFL;
		each(i, signs) {
			int col = i->second;
			int left2 = INF, right2 = -INF;
			ll x = 0;
			each(j, signs) if(j->second != col) {
				amin(left2, j->first);
				amax(right2, j->first);
				x += abs(j->second - col);
			}
			x += left2 == INF ? 0 : solve(left2, right2);
			amin(naiveans, x);
		}
		if(ans != naiveans)
			cerr << ans << " != " << naiveans << endl;*/

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

Submission Info

Compile Error

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