Submission #3623458

Source Code Expand

Copy
```#include <bits/stdc++.h>
using namespace std;

template<typename T>
struct Segtree {
int n;
T e;
vector<T> dat;
typedef function<T(T a, T b)> Func;
Func f;

Segtree(){}
Segtree(int n_input, Func f_input, T e_input){
initialize(n_input, f_input, e_input);
}
void initialize(int n_input, Func f_input, T e_input){
f = f_input;
e = e_input;
n = 1;
while(n < n_input) n <<= 1;
dat.resize(2*n-1, e);
}

void update(int k, T a){
k += n - 1;
dat[k] = a;
while(k > 0){
k = (k - 1)/2;
dat[k] = f(dat[2*k+1], dat[2*k+2]);
}
}

T get(int k){
return dat[k+n-1];
}

T between(int a, int b){
return query(a, b+1, 0, 0, n);
}

T query(int a, int b, int k, int l, int r){
if(r<=a || b<=l) return e;
if(a<=l && r<=b) return dat[k];
T vl = query(a, b, 2*k+1, l, (l+r)/2);
T vr = query(a, b, 2*k+2, (l+r)/2, r);
return f(vl, vr);
}
};

template<typename T>
struct LazySegtree {
int n;
T e;
vector<T> dat, laz;
typedef function<T(T a, T b)> Func;
Func f;

LazySegtree(int n_input, Func f, T e_input, const vector<int>& v):f(f), e(e_input){
n = 1;
while(n < n_input) n <<= 1;
dat.resize(2*n-1, e);
laz.resize(2*n-1, 0);
for(int i=0; i<n_input; i++) dat[i+n-1] = v[i];
for(int i=n-2; i>=0; i--) dat[i] = f(dat[2*i+1], dat[2*i+2]);
}

void eval(int k, int l, int r){
if(laz[k] == 0) return;
dat[k] += laz[k];
if(r-l > 1){
laz[2*k+1] += laz[k];
laz[2*k+2] += laz[k];
}
laz[k] = 0;
}

void add_between(int a, int b, T x){
add(a, b+1, x, 0, 0, n);
}

void add(int a, int b, T x, int k, int l, int r){
eval(k, l, r);
if(b <= l || r <= a) return;
if(a <= l && r <= b){
laz[k] += x;
eval(k, l, r);
}else{
add(a, b, x, 2*k+1, l, (l+r)/2);
add(a, b, x, 2*k+2, (l+r)/2, r);
dat[k] = f(dat[2*k+1], dat[2*k+2]);
}
}

T get_between(int a, int b){
return query(a, b+1, 0, 0, n);
}

T query(int a, int b, int k, int l, int r){
eval(k, l, r);
if(r<=a || b<=l) return e;
if(a<=l && r<=b) return dat[k];
T vl = query(a, b, 2*k+1, l, (l+r)/2);
T vr = query(a, b, 2*k+2, (l+r)/2, r);
return f(vl, vr);
}
};

int main(){
int N, K, T[100000], A[100000];
cin >> N >> K;
for(int i=0; i<N; i++) cin >> T[i] >> A[i];

typedef pair<int, int> P;
Segtree<P> stval[2];
for(int k=0; k<2; k++) stval[k].initialize(N, [](P a, P b){return min(a, b); }, {1e9+1, 0});

vector<int> sums(N);
for(int i=0; i<N; i++){
stval[T[i]].update(i, {A[i], -i});
sums[i] = (T[i] ? 1 : -1) + (i>0 ? sums[i-1] : 0);
}
LazySegtree<int> stmin(N, [](int a, int b){return min(a, b);}, 1e9, sums);
LazySegtree<int> stmax(N, [](int a, int b){return max(a, b);}, -1, sums);

int64_t ans = 0;
int sum = 0;
for(int i=0; i<N; i++){
sum += (T[i] ? 1 : -1);
ans += A[i];
if(sum > K){
int ok = i, ng = -1;
while(ok-ng>1){
int mid = (ng+ok)/2;
(stmin.get_between(mid, i) > 0 ? ok : ng) = mid;
}
int del = -stval[T[i]].between(ok, i).second;
ans -= A[del];
stval[T[i]].update(del, {1e9+1, 0});
sum--;
}else if(sum < 0){
int ok = i, ng = -1;
while(ok-ng>1){
int mid = (ng+ok)/2;
(stmax.get_between(mid, i) < K ? ok : ng) = mid;
}
int del = -stval[T[i]].between(ok, i).second;
ans -= A[del];
stval[T[i]].update(del, {1e9+1, 0});
sum++;
}
}
cout << ans << endl;
return 0;
}```

#### Submission Info

Submission Time 2018-11-18 22:33:11+0900 F - Dinner Planning betrue12 C++14 (GCC 5.4.1) 600 4354 Byte AC 244 ms 9600 KB

#### Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample_01.txt, sample_02.txt, sample_03.txt
All 600 / 600 big_01.txt, big_02.txt, big_03.txt, sample_01.txt, sample_02.txt, sample_03.txt, small_01.txt, small_02.txt, small_03.txt, tiny_01.txt
Case Name Status Exec Time Memory
big_01.txt 244 ms 9600 KB
big_02.txt 213 ms 9600 KB
big_03.txt 229 ms 9600 KB
sample_01.txt 1 ms 256 KB
sample_02.txt 1 ms 256 KB
sample_03.txt 1 ms 256 KB
small_01.txt 1 ms 256 KB
small_02.txt 1 ms 256 KB
small_03.txt 1 ms 256 KB
tiny_01.txt 1 ms 256 KB