Submission #783181


Source Code Expand

#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define all(c) (c).begin(),(c).end()
#define mp make_pair
#define pb push_back
#define dbg(...) do{cerr<<__LINE__<<": ";dbgprint(#__VA_ARGS__, __VA_ARGS__);}while(0);

using namespace std;

namespace std{template<class S,class T>struct hash<pair<S,T>>{size_t operator()(const pair<S,T>&p)const{return ((size_t)1e9+7)*hash<S>()(p.first)+hash<T>()(p.second);}};template<class T>struct hash<vector<T>>{size_t operator()(const vector<T> &v)const{size_t h=0;for(auto i : v)h=h*((size_t)1e9+7)+hash<T>()(i)+1;return h;}};}
template<class T>ostream& operator<<(ostream &os, const vector<T> &v){os<<"[ ";rep(i,v.size())os<<v[i]<<(i==v.size()-1?" ]":", ");return os;}template<class T>ostream& operator<<(ostream &os,const set<T> &v){os<<"{ "; for(const auto &i:v)os<<i<<", ";return os<<"}";}
template<class T,class U>ostream& operator<<(ostream &os,const map<T,U> &v){os<<"{";for(const auto &i:v)os<<" "<<i.first<<": "<<i.second<<",";return os<<"}";}template<class T,class U>ostream& operator<<(ostream &os,const pair<T,U> &p){return os<<"("<<p.first<<", "<<p.second<<")";}
void dbgprint(const string &fmt){cerr<<endl;}template<class H,class... T>void dbgprint(const string &fmt,const H &h,const T&... r){cerr<<fmt.substr(0,fmt.find(","))<<"= "<<h<<" ";dbgprint(fmt.substr(fmt.find(",")+1),r...);}
typedef long long ll;typedef vector<int> vi;typedef pair<int,int> pi;const int inf = (int)1e9;const double INF = 1e12, EPS = 1e-9;
inline int xor128(){
	//static int w = (unsigned int)time(NULL);
	static int w = 88675123;
	static int x = 123456789, y = 362436069, z = 521288629;
	int t = x ^ x << 11;
	x = y; y = z; z = w;
	return w = w ^ w >> 19 ^ t ^ t >> 8;
}
const int N = 210000;
set<pi> rightmost, leftmost; //(-pos, col), (pos, col)
set<int> pos[N];

//色のbit, 色の総和のbit
ll bit_cnt[N], bit_sum[N];
inline ll sum(ll *bit, int i){
	ll res = 0;
	for(i++; i; i -= i & -i) res += bit[i];
	return res;
}
inline void add(ll *bit, int i, ll x){
	for(i++; i < N; i += i & -i) bit[i] += x;
}
ll median_color(){ //色の中央値
	ll *bit = bit_cnt;
	int k = (sum(bit_cnt, N - 2) + 1) / 2, kk = k;
	int lo = 0, hi = 1 << 32 - __builtin_clz(N), mid;
	while(lo + 1 < hi){
		mid = (lo + hi) / 2;
		if(mid >= N || bit[mid] >= k) hi = mid;
		else k -= bit[lo = mid];
	}
	/*
	rep(i, N) if(pos[i].size()) dbg(i, pos[i]);
	rep(i, 10) cerr<<sum(bit, i) - sum(bit, i-1)<<(i==9?"\n":" ");
	dbg(hi, kk);
	ll xx = sum(bit, hi - 1);
	ll yy = (hi - 2 >= 0 ? sum(bit, hi - 2) : 0);
	dbg(xx, yy);
	assert(sum(bit, hi - 1) >= kk);
	assert((hi - 2 >= 0 ? sum(bit, hi - 2) : 0) < kk);
	*/
	return hi - 1;
}
inline void del(int x, int col){
	add(bit_cnt, col, -1);
	add(bit_sum, col, -col);
	rightmost.erase(mp(-x, col)); leftmost.erase(mp(x, col));
	pos[col].erase(x);
	if(pos[col].empty()) return;
	rightmost.insert(mp(-*pos[col].rbegin(), col));
	leftmost.insert(mp(*pos[col].begin(), col));
}
inline void ins(int x, int col){
	if(!pos[col].empty()){
		rightmost.erase(mp(-*pos[col].rbegin(), col));
		leftmost.erase(mp(*pos[col].begin(), col));
	}
	pos[col].insert(x);
	rightmost.insert(mp(-*pos[col].rbegin(), col));
	leftmost.insert(mp(*pos[col].begin(), col));
	add(bit_cnt, col, 1);
	add(bit_sum, col, col);
}
pair<vector<pi>,vector<pi>> getpos(){
	vector<pi> l, r;
	for(const auto &p : leftmost){
		l.pb(p);
		if(l.size() == 2) break;
	}
	for(const auto &p : rightmost){
		r.pb(mp(-p.first, p.second));
		if(r.size() == 2) break;
	}
	return mp(l, r);
}
ll calc_sum(vector<pi> l, vector<pi> r, int col){
	int lpos = l[0].second == col ? l.size() > 1 ? l[1].first : inf : l[0].first;
	int rpos = r[0].second == col ? r.size() > 1 ? r[1].first :-inf : r[0].first;
	if(lpos == inf || rpos == -inf) return 0;
	rpos = max(rpos, 0);
	lpos = -min(lpos, 0);
	ll res = 2ll * min(lpos, rpos) + max(lpos, rpos);
	
	//色
	int lcnt = sum(bit_cnt, col - 1);
	int rcnt = sum(bit_cnt, N - 2) - sum(bit_cnt, col);
	ll lsum  = sum(bit_sum, col - 1);
	ll rsum  = sum(bit_sum, N - 2) - sum(bit_sum, col);
	
	res += rsum - (ll)col * rcnt + (ll)col * lcnt - lsum;
	return res;
}
ll query(){
	ll res = 1e18;
	vector<pi> l, r;
	tie(l, r) = getpos();
	
	vi cols(1, median_color());
	for(pi p : l) cols.pb(p.second); for(pi p : r) cols.pb(p.second);
	sort(all(cols)); cols.erase(unique(all(cols)), cols.end());
	
	for(int col : cols) res = min(res, calc_sum(l, r, col));
	return res;
}
int n, q, x[N], a[N], c[N], y[N], b[N]; vector<ll> ans_naive, ans_;

void solve_naive(){
	vector<pi> kan;
	rep(i, n) kan.pb(mp(x[i], a[i]));
	rep(i, q){
		if(c[i] == 1) kan.pb(mp(y[i], b[i]));
		else{
			rep(j, kan.size()) if(kan[j] == mp(y[i], b[i])){
				kan.erase(kan.begin() + j); break;
			}
		}
		//dbg(kan);
		
		ll ans = 1e18;
		rep(col, kan.size()){
			ll r = 0, l = 0, sum = 0;
			rep(i, kan.size()) if(kan[i].second != kan[col].second){
				r = max(r, (ll)kan[i].first);
				l = min(l, (ll)kan[i].first);
				sum += abs(kan[i].second - kan[col].second);
			}
			l = -l;
			sum += min(l, r) * 2 + max(l, r);
			ans = min(ans, sum);
		}
		ans_naive.pb(ans); //cout << ans << endl;
	}
}
void solve(){
	rep(i, n) ins(x[i], a[i]);
	rep(i, q){
		//dbg(i, q, y[i], b[i]);
		if(c[i] == 1) ins(y[i], b[i]);
		else del(y[i], b[i]);
		//ans_.pb(query());
		printf("%lld\n", query());
	}
}

int main(){
	#if 1
	scanf("%d", &n);
	rep(i, n) scanf("%d%d", x + i, a + i);
	scanf("%d", &q);
	rep(i, q) scanf("%d%d%d", c + i, y + i, b + i);
	
	//solve_naive();
	solve();
	#else
	rep(it, 1){
		n = 5;
		rep(i, n) x[i] = xor128() % 1001 - 500;
		rep(i, n) a[i] = xor128() % 201;
		q = 200;
		rep(i, q) c[i] = 1;
		rep(i, q){
			RE:
			y[i] = xor128() % 2001 - 1000;
			rep(j, n) if(x[j] == y[i]) goto RE;
			rep(j, i) if(y[j] == y[i]) goto RE;
		}
		rep(i, q) b[i] = xor128() % 201;
		solve_naive(); cerr<<endl;
		solve();
		
		rep(i, q) cerr<<ans_naive[i]<<" "<<ans_[i]<<"      "<<(ans_naive[i]==ans_[i])<<endl;
	}
	#endif
	return 0;
}

Submission Info

Submission Time
Task J - 看板の塗り替え
User nadeko
Language C++11 (GCC 4.9.2)
Score 300
Code Size 6127 Byte
Status AC
Exec Time 858 ms
Memory 44060 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:161:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
./Main.cpp:162:39: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  rep(i, n) scanf("%d%d", x + i, a + i);
                                       ^
./Main.cpp:163:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
                 ^
./Main.cpp:164:48: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  rep(i, q) scanf("%d%d%d", c + i, y + i, b + i);
                                                ^

Judge Result

Set Name Subtask All
Score / Max Score 30 / 30 270 / 270
Status
AC × 26
AC × 53
Set Name Test Cases
Subtask subtask_00.txt, subtask_01.txt, subtask_02.txt, subtask_03.txt, subtask_04.txt, subtask_05.txt, subtask_06.txt, subtask_07.txt, subtask_08.txt, subtask_09.txt, subtask_10.txt, subtask_11.txt, subtask_12.txt, subtask_13.txt, subtask_14.txt, subtask_15.txt, subtask_16.txt, subtask_17.txt, subtask_18.txt, subtask_19.txt, subtask_20.txt, subtask_21.txt, subtask_22.txt, subtask_23.txt, subtask_24.txt, subtask_25.txt
All scrambled_00.txt, scrambled_01.txt, scrambled_02.txt, scrambled_03.txt, scrambled_04.txt, scrambled_05.txt, scrambled_06.txt, scrambled_07.txt, scrambled_08.txt, scrambled_09.txt, scrambled_10.txt, scrambled_11.txt, scrambled_12.txt, scrambled_13.txt, scrambled_14.txt, scrambled_15.txt, scrambled_16.txt, scrambled_17.txt, scrambled_18.txt, scrambled_19.txt, scrambled_20.txt, scrambled_21.txt, scrambled_22.txt, scrambled_23.txt, scrambled_24.txt, scrambled_25.txt, scrambled_26.txt, subtask_00.txt, subtask_01.txt, subtask_02.txt, subtask_03.txt, subtask_04.txt, subtask_05.txt, subtask_06.txt, subtask_07.txt, subtask_08.txt, subtask_09.txt, subtask_10.txt, subtask_11.txt, subtask_12.txt, subtask_13.txt, subtask_14.txt, subtask_15.txt, subtask_16.txt, subtask_17.txt, subtask_18.txt, subtask_19.txt, subtask_20.txt, subtask_21.txt, subtask_22.txt, subtask_23.txt, subtask_24.txt, subtask_25.txt
Case Name Status Exec Time Memory
scrambled_00.txt AC 95 ms 10984 KB
scrambled_01.txt AC 858 ms 37212 KB
scrambled_02.txt AC 550 ms 29008 KB
scrambled_03.txt AC 385 ms 27068 KB
scrambled_04.txt AC 267 ms 22824 KB
scrambled_05.txt AC 312 ms 27048 KB
scrambled_06.txt AC 704 ms 27984 KB
scrambled_07.txt AC 108 ms 16036 KB
scrambled_08.txt AC 597 ms 26956 KB
scrambled_09.txt AC 334 ms 22056 KB
scrambled_10.txt AC 148 ms 20020 KB
scrambled_11.txt AC 374 ms 17568 KB
scrambled_12.txt AC 252 ms 16268 KB
scrambled_13.txt AC 125 ms 12452 KB
scrambled_14.txt AC 183 ms 15780 KB
scrambled_15.txt AC 149 ms 12840 KB
scrambled_16.txt AC 502 ms 17576 KB
scrambled_17.txt AC 292 ms 14764 KB
scrambled_18.txt AC 148 ms 13096 KB
scrambled_19.txt AC 297 ms 13352 KB
scrambled_20.txt AC 170 ms 12836 KB
scrambled_21.txt AC 795 ms 44060 KB
scrambled_22.txt AC 743 ms 28068 KB
scrambled_23.txt AC 191 ms 17348 KB
scrambled_24.txt AC 565 ms 25248 KB
scrambled_25.txt AC 424 ms 22180 KB
scrambled_26.txt AC 469 ms 16780 KB
subtask_00.txt AC 63 ms 14644 KB
subtask_01.txt AC 62 ms 14492 KB
subtask_02.txt AC 60 ms 14244 KB
subtask_03.txt AC 58 ms 14140 KB
subtask_04.txt AC 59 ms 14244 KB
subtask_05.txt AC 65 ms 14244 KB
subtask_06.txt AC 58 ms 14120 KB
subtask_07.txt AC 66 ms 14248 KB
subtask_08.txt AC 56 ms 13864 KB
subtask_09.txt AC 59 ms 13924 KB
subtask_10.txt AC 57 ms 11044 KB
subtask_11.txt AC 49 ms 10920 KB
subtask_12.txt AC 53 ms 11044 KB
subtask_13.txt AC 51 ms 10920 KB
subtask_14.txt AC 50 ms 10924 KB
subtask_15.txt AC 58 ms 11156 KB
subtask_16.txt AC 54 ms 11308 KB
subtask_17.txt AC 55 ms 11180 KB
subtask_18.txt AC 52 ms 11180 KB
subtask_19.txt AC 54 ms 11076 KB
subtask_20.txt AC 59 ms 11560 KB
subtask_21.txt AC 64 ms 14260 KB
subtask_22.txt AC 57 ms 14124 KB
subtask_23.txt AC 61 ms 14048 KB
subtask_24.txt AC 58 ms 14116 KB
subtask_25.txt AC 61 ms 14124 KB