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
2016-06-29 08:43:16+0900
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
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