Submission #538179

#	Time	Username	Problem	Language	Result	Execution time	Memory
538179		wiwiho	Treatment Project (JOI20_treatment)	C++14	100 / 100	698 ms	103348 KiB

treatment

#include <bits/stdc++.h>
#include <bits/extc++.h>

#define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define iter(a) a.begin(), a.end()
#define riter(a) a.rbegin(), a.rend()
#define lsort(a) sort(iter(a))
#define gsort(a) sort(riter(a))
#define pb(a) push_back(a)
#define eb(a) emplace_back(a)
#define pf(a) push_front(a)
#define ef(a) emplace_front(a)
#define pob pop_back()
#define pof pop_front()
#define mp(a, b) make_pair(a, b)
#define F first
#define S second
#define mt make_tuple
#define gt(t, i) get<i>(t)
#define tomax(a, b) ((a) = max((a), (b)))
#define tomin(a, b) ((a) = min((a), (b)))
#define topos(a) ((a) = (((a) % MOD + MOD) % MOD))
#define uni(a) a.resize(unique(iter(a)) - a.begin())
#define printv(a, b) {bool pvaspace=false; \
for(auto pva : a){ \
    if(pvaspace) b << " "; pvaspace=true;\
    b << pva;\
}\
b << "\n";}

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdd = pair<ld, ld>;
using tiii = tuple<int, int, int>;

const ll MOD = 1000000007;
const ll MAX = 1LL << 60;

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

ll ifloor(ll a, ll b){
    if(b < 0) a *= -1, b *= -1;
    if(a < 0) return (a - b + 1) / b;
    else return a / b;
}

ll iceil(ll a, ll b){
    if(b < 0) a *= -1, b *= -1;
    if(a > 0) return (a + b - 1) / b;
    else return a / b;
}

struct treat{
    ll t, l, r, c;
};

int n, K, m;
vector<ll> dis;
vector<treat> a;
std::priority_queue<pll, vector<pll>, greater<>> pq;

#define lc (2 * id + 1)
#define rc (2 * id + 2)

struct SegmentTree{
    vector<vector<pll>> st;

    void init(){
        st.resize(4 * m);
    }

    void add(int x, pll v, int L = 0, int R = m - 1, int id = 0){
        //cerr << "add " << v << " " << id << "\n";
        st[id].eb(v);
        if(L == R){
            return;
        }
        int M = (L + R) / 2;
        if(x <= M) add(x, v, L, M, lc);
        else add(x, v, M + 1, R, rc);
    }

    void relax(int l, int r, int mx, ll d, int L = 0, int R = m - 1, int id = 0){
        if(l <= L && R <= r){
            //cerr << "sgt relax " << l << " " << r << " " << L << " " << R << " " << id << "\n";
            //printv(st[id], cerr);
            while(!st[id].empty() && st[id].back().F <= mx){
                int now = st[id].back().S;
                if(dis[now] <= d + a[now].c){
                    st[id].pob;
                    continue;
                }
                //cerr << "ok " << now << "\n";
                dis[now] = d + a[now].c;
                pq.push(mp(dis[now], now));
                st[id].pob;
            }
            return;
        }
        int M = (L + R) / 2;
        if(r <= M) relax(l, r, mx, d, L, M, lc);
        else if(l > M) relax(l, r, mx, d, M + 1, R, rc);
        else{
            relax(l, r, mx, d, L, M, lc);
            relax(l, r, mx, d, M + 1, R, rc);
        }
    }

};

int main(){
    StarBurstStream

    cin >> n >> K;
    a.resize(K + 1);
    dis.resize(K + 1, MAX);

    vector<int> tmp;

    SegmentTree st1, st2;

    for(int i = 1; i <= K; i++){
        cin >> a[i].t >> a[i].l >> a[i].r >> a[i].c;
        tmp.eb(a[i].t);
    }
    lsort(tmp);
    uni(tmp);
    m = tmp.size();
    st1.init(); st2.init();

    for(int i = 1; i <= K; i++){
        int x = lower_bound(iter(tmp), a[i].t) - tmp.begin();
        st1.add(x, mp(-(a[i].t - a[i].l), i));
        st2.add(x, mp(a[i].t + a[i].l, i));
    }

    for(int i = 0; i < 4 * m; i++){
        gsort(st1.st[i]);
        gsort(st2.st[i]);
    }

    for(int i = 1; i <= K; i++){
        if(a[i].l == 1){
            dis[i] = a[i].c;
            pq.push(mp(a[i].c, i));
        }
    }
    
    while(!pq.empty()){
        int now = pq.top().S;
        ll d = pq.top().F;
        pq.pop();
        if(d != dis[now]) continue;
        int x = lower_bound(iter(tmp), a[now].t) - tmp.begin();
        //cerr << "relax1 " << now << "\n";
        st1.relax(0, x, -(a[now].t - a[now].r - 1), d);
        //cerr << "relax2 " << now << "\n";
        st2.relax(x, m - 1, a[now].r + a[now].t + 1, d);
    }

    ll ans = MAX;
    for(int i = 1; i <= K; i++){
        if(a[i].r == n){
            ans = min(ans, dis[i]);
        }
    }
    if(ans == MAX) ans = -1;
    cout << ans << "\n";

    return 0;
}

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