Submission #3887991
Source Code Expand
#include <bits/stdc++.h>
#define ll long long
#define INF 1000000005
#define MOD 1000000007
#define EPS 1e-10
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;--i)
#define srep(i,s,t) for(int i=(int)(s);i<(int)(t);++i)
#define each(a,b) for(auto& (a): (b))
#define all(v) (v).begin(),(v).end()
#define len(v) (int)(v).size()
#define zip(v) sort(all(v)),v.erase(unique(all(v)),v.end())
#define cmx(x,y) x=max(x,y)
#define cmn(x,y) x=min(x,y)
#define fi first
#define se second
#define pb push_back
#define show(x) cout<<#x<<" = "<<(x)<<endl
#define spair(p) cout<<#p<<": "<<p.fi<<" "<<p.se<<endl
#define sar(a,n) cout<<#a<<":";rep(pachico,n)cout<<" "<<a[pachico];cout<<endl
#define svec(v) cout<<#v<<":";rep(pachico,v.size())cout<<" "<<v[pachico];cout<<endl
#define svecp(v) cout<<#v<<":";each(pachico,v)cout<<" {"<<pachico.first<<":"<<pachico.second<<"}";cout<<endl
#define sset(s) cout<<#s<<":";each(pachico,s)cout<<" "<<pachico;cout<<endl
#define smap(m) cout<<#m<<":";each(pachico,m)cout<<" {"<<pachico.first<<":"<<pachico.second<<"}";cout<<endl
#define int long long
using namespace std;
typedef pair<int,int> P;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<P> vp;
typedef vector<string> vs;
const int MAX_N = 200005;
set<P> st;
set<int> pl[MAX_N];
template<typename V> class BIT {
private:
int n; vector<V> bit;
public:
void add(int i,V x){ i++; while(i < n) bit[i] += x, i += i & -i;}
V sum(int i){ i++; V s = 0; while(i>0) s += bit[i], i -= i & -i; return s;} //0_indexedで[0,i]の要素の和
BIT(){} BIT(int sz){ n = sz + 1, bit.resize(n,0);} //初期値がすべて0の場合
BIT(vector<V>& v){ n = (int)v.size()+1; bit.resize(n, 0); rep(i,n-1) add(i,v[i]);}
void resize(int sz){ n = sz + 1, bit.resize(n,0); }
void print(){ rep(i,n-1)cout<<sum(i)-sum(i-1)<< " ";cout<<endl;}
void print_sum(){ rep(i,n)cout<<sum(i-1)<<" ";cout<<endl;} //-1スタート
};
template<typename T> class segtree1 {
private:
int n,sz;
vector<T> node;
public:
segtree1(vector<T>& v){
sz = (int)v.size();
n = 1;
while(n < sz){
n *= 2;
}
node.assign(2*n,numeric_limits<T>::max());
rep(i,sz){
node[i+n] = v[i];
}
for(int i=n-1; i>=1; i--){
node[i] = min(node[2*i],node[2*i+1]);
}
}
void update(int k,T a)
{
node[k+=n] = a;
while(k>>=1){
node[k] = min(node[2*k],node[2*k+1]);
}
}
T query(int a,int b)
{
T res1 = numeric_limits<T>::max();
T res2 = numeric_limits<T>::max();
a += n, b += n;
while(a != b){
if(a % 2) res1 = min(res1, node[a++]);
if(b % 2) res2 = min(res2, node[--b]);
a >>= 1, b>>= 1;
}
return min(res1, res2);
}
void print()
{
rep(i,sz){
cout << query(i,i+1) << " ";
}
cout << endl;
}
};
template<typename T> class segtree2 {
private:
int n,sz;
vector<T> node;
public:
segtree2(vector<T>& v){
sz = (int)v.size();
n = 1;
while(n < sz){
n *= 2;
}
node.assign(2*n,numeric_limits<T>::min());
rep(i,sz){
node[i+n] = v[i];
}
for(int i=n-1; i>=1; i--){
node[i] = max(node[2*i],node[2*i+1]);
}
}
void update(int k, T a)
{
node[k+=n] = a;
while(k>>=1){
node[k] = max(node[2*k],node[2*k+1]);
}
}
T query(int a,int b)
{
T res1 = numeric_limits<T>::min();
T res2 = numeric_limits<T>::min();
a += n, b += n;
while(a != b){
if(a % 2) res1 = max(res1, node[a++]);
if(b % 2) res2 = max(res2, node[--b]);
a >>= 1, b>>= 1;
}
return max(res1, res2);
}
void print()
{
rep(i,sz){
cout << query(i,i+1) << " ";
}
cout << endl;
}
};
BIT<ll> bt;
BIT<int> cnt;
ll calc(int pos)
{
ll x1 = bt.sum(pos), x2 = bt.sum(199999);
ll y1 = cnt.sum(pos), y2 = cnt.sum(199999);
return (ll)pos * y1 - x1 + (x2-x1) - (ll)pos * (y2-y1);
}
P get(int kind, segtree1<int>& sg1, segtree2<int>& sg2)
{
return P(min(sg1.query(0, kind), sg1.query(kind+1, 200000)), max(sg2.query(0, kind), sg2.query(kind+1, 200000)));
}
ll dif(int num){
return calc(num+1)-calc(num);
}
ll solve()
{
int l = 0, h = 199999LL;
if(dif(l) > 0){
return calc(l);
}
while(h-l>1){
int mid=(l+h)/2;
if(dif(mid) >= 0){
l = mid;
}else{
h = mid;
}
}
return min(calc(l), calc(min(h,199999LL)));
// ll fl = calc(l);
// while(h-l>2){
// int m1 = (2*l+h)/3, m2 = (l+2*h)/3;
// ll f1 = calc(m1), f2 = calc(m2);
// if(f1 == f2) return f1;
// if(f1 < f2){
// h = m2;
// }else{
// l = m1, fl = f1;
// }
// }
// return min({fl, fl+1, calc(min(h, 199999LL))});
}
signed main()
{
cin.tie(0);
ios::sync_with_stdio(false);
int n;
cin >> n;
bt.resize(200000), cnt.resize(200000);
vi hoge1(200000, INF), hoge2(200000, -INF);
segtree1<int> left(hoge1);
segtree2<int> right(hoge2);
rep(i,n){
int x,a;
cin >> x >> a;
--a;
st.insert(P(x, a));
pl[a].insert(x);
if(*(--pl[a].end()) == x){
right.update(a, x);
}
if(*pl[a].begin() == x){
left.update(a, x);
}
bt.add(a,a), cnt.add(a,1);
}
int q;
cin >> q;
rep(i,q){
int c,a,b;
cin >> c >> a >> b;
--b;
if(c == 1){
st.insert(P(a, b));
pl[b].insert(a);
if(*(--pl[b].end()) == a){
right.update(b, a);
}
if(*pl[b].begin() == a){
left.update(b, a);
}
bt.add(b,b);
cnt.add(b,1);
}else{
st.erase(P(a, b));
if((int)pl[b].size() == 1){
right.update(b, -INF), left.update(b, INF);
}else{
if(*(--pl[b].end()) == a){
right.update(b, *(--(--pl[b].end())));
}
if(*pl[b].begin() == a){
left.update(b, *(++pl[b].begin()));
}
}
pl[b].erase(a);
bt.add(b,-b);
cnt.add(b,-1);
}
// 右端に変えたとき
int c1 = (*(--st.end())).se;
P p1 = get(c1, left, right);
if(p1.fi == INF){
cout << "0\n";
continue;
}
ll ans1 = p1.se-p1.fi+min(max(-p1.fi,p1.fi),max(-p1.se,p1.se)) + calc(c1);
// 左端に変えたとき
int c2 = (*st.begin()).se;
P p2 = get(c2, left, right);
if(p2.fi == INF){
cout << "0\n";
continue;
}
ll ans2 = p2.se-p2.fi+min(max(-p2.fi,p2.fi),max(-p2.se,p2.se)) + calc(c2);
int L = (*st.begin()).fi, R = (*(--st.end())).fi;
ll ans3 = R-L+min(max(-L,L),max(-R,R)) + solve();
cout << min({ans1, ans2, ans3}) << "\n";
}
return 0;
}
Submission Info
Submission Time |
|
Task |
J - 看板の塗り替え |
User |
kopricky |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
7635 Byte |
Status |
WA |
Exec Time |
478 ms |
Memory |
47104 KB |
Judge Result
Set Name |
Subtask |
All |
Score / Max Score |
0 / 30 |
0 / 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 |
14 ms |
24064 KB |
scrambled_01.txt |
WA |
478 ms |
47104 KB |
scrambled_02.txt |
WA |
304 ms |
37888 KB |
scrambled_03.txt |
WA |
194 ms |
35456 KB |
scrambled_04.txt |
WA |
126 ms |
31616 KB |
scrambled_05.txt |
WA |
146 ms |
35328 KB |
scrambled_06.txt |
WA |
359 ms |
36096 KB |
scrambled_07.txt |
WA |
45 ms |
25728 KB |
scrambled_08.txt |
WA |
347 ms |
35072 KB |
scrambled_09.txt |
WA |
169 ms |
30592 KB |
scrambled_10.txt |
WA |
69 ms |
28800 KB |
scrambled_11.txt |
AC |
213 ms |
35200 KB |
scrambled_12.txt |
AC |
143 ms |
33920 KB |
scrambled_13.txt |
AC |
56 ms |
26752 KB |
scrambled_14.txt |
AC |
116 ms |
33536 KB |
scrambled_15.txt |
AC |
71 ms |
27392 KB |
scrambled_16.txt |
WA |
365 ms |
36096 KB |
scrambled_17.txt |
WA |
198 ms |
31104 KB |
scrambled_18.txt |
WA |
82 ms |
27776 KB |
scrambled_19.txt |
WA |
183 ms |
28032 KB |
scrambled_20.txt |
WA |
96 ms |
27392 KB |
scrambled_21.txt |
WA |
429 ms |
47104 KB |
scrambled_22.txt |
WA |
400 ms |
36096 KB |
scrambled_23.txt |
WA |
91 ms |
26752 KB |
scrambled_24.txt |
WA |
280 ms |
33536 KB |
scrambled_25.txt |
WA |
233 ms |
30848 KB |
scrambled_26.txt |
WA |
247 ms |
26368 KB |
subtask_00.txt |
WA |
20 ms |
24576 KB |
subtask_01.txt |
AC |
19 ms |
24448 KB |
subtask_02.txt |
WA |
18 ms |
24320 KB |
subtask_03.txt |
WA |
15 ms |
24192 KB |
subtask_04.txt |
WA |
16 ms |
24320 KB |
subtask_05.txt |
WA |
19 ms |
24320 KB |
subtask_06.txt |
WA |
15 ms |
24192 KB |
subtask_07.txt |
WA |
19 ms |
24320 KB |
subtask_08.txt |
AC |
14 ms |
24192 KB |
subtask_09.txt |
WA |
15 ms |
24192 KB |
subtask_10.txt |
AC |
16 ms |
24320 KB |
subtask_11.txt |
AC |
14 ms |
24064 KB |
subtask_12.txt |
AC |
15 ms |
24320 KB |
subtask_13.txt |
AC |
14 ms |
24192 KB |
subtask_14.txt |
AC |
14 ms |
24064 KB |
subtask_15.txt |
AC |
19 ms |
24320 KB |
subtask_16.txt |
WA |
16 ms |
24320 KB |
subtask_17.txt |
AC |
16 ms |
24320 KB |
subtask_18.txt |
AC |
14 ms |
24192 KB |
subtask_19.txt |
AC |
18 ms |
24320 KB |
subtask_20.txt |
AC |
20 ms |
24576 KB |
subtask_21.txt |
WA |
20 ms |
24320 KB |
subtask_22.txt |
WA |
17 ms |
24192 KB |
subtask_23.txt |
WA |
18 ms |
24192 KB |
subtask_24.txt |
AC |
15 ms |
24192 KB |
subtask_25.txt |
WA |
17 ms |
24192 KB |