Submission #537398

#	Time	Username	Problem	Language	Result	Execution time	Memory
537398		wiwiho	Treatment Project (JOI20_treatment)	C++14	4 / 100	79 ms	3632 KiB

treatment

#include <bits/stdc++.h>

#define mp make_pair
#define F first
#define S second
#define eb emplace_back
#define iter(a) a.begin(), a.end()
#define lsort(a) sort(iter(a))
#define gsort(a) sort(iter(a), greater<>())
#define printv(a, b) { \
    for(auto pv : a) b << pv << " "; \
    b << "\n"; \
}

using namespace std;

typedef long long ll;
using pii = pair<int, int>;

template<typename A, typename B>
ostream& operator<<(ostream& o, pair<A, B> a){
    return o << '(' << a.F << ',' << a.S << ')';
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, m;
    cin >> n >> m;

    map<int, ll> dp;
    vector<pair<int, pii>> ev;
    for(int i = 1; i <= m; i++){
        int l, r, c, t;
        cin >> t >> l >> r >> c;
        assert(t == 1);
        ev.eb(mp(l, mp(r, c)));
    }
    //cerr << "ok\n";
    lsort(ev);

    dp[0] = 0;
    for(auto i : ev){
        int l = i.F;
        int r = i.S.F;
        ll c = i.S.S;
        while(!dp.empty() && dp.begin()->F < l - 1) dp.erase(dp.begin());
        if(dp.empty()) break;
        //cerr << "test " << l << " " << r << " " << c << "\n";
        //printv(dp, cerr);
        c += dp.begin()->S;
        if(dp.find(r) == dp.end()) dp[r] = c;
        else dp[r] = min(dp[r], c);
        auto it = dp.lower_bound(r);
        while(it != dp.begin() && prev(it)->S >= c){
            it = dp.erase(prev(it));
        }
        if(next(it) != dp.end() && next(it)->S <= c) dp.erase(it);
        //cerr << "test " << l << " " << r << " " << c << "\n";
        //printv(dp, cerr);
    }

    if(dp.empty() || dp.rbegin()->F != n){
        cout << "-1\n";
        return 0;
    }
    cout << dp.rbegin()->S << "\n";

    return 0;
}

• Subtask 1: 4 / 4
• Subtask 2: 0 / 5
• Subtask 3: 0 / 30
• Subtask 4: 0 / 61