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});
            stmin.add_between(del, N-1, -1);
            stmax.add_between(del, N-1, -1);
            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});
            stmin.add_between(del, N-1, 1);
            stmax.add_between(del, N-1, 1);
            sum++;
        }
    }
    cout << ans << endl;
    return 0;
}

Submission Info

Submission Time
Task F - Dinner Planning
User betrue12
Language C++14 (GCC 5.4.1)
Score 600
Code Size 4354 Byte
Status
Exec Time 244 ms
Memory 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