Submission #1100236

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100236		_8_8_	Treatment Project (JOI20_treatment)	C++17	100 / 100	2703 ms	306288 KiB

treatment

#include <bits/stdc++.h>
    
using namespace std;
    
typedef long long ll;
    
const int  N = 2e5 + 12, MOD = (int)1e9 + 7;
    
const ll inf = 1e18;
ll res = inf, d[N];
int n, m, s;
struct tr{
    ll t, l, r, c;
}; 
vector<int> T;
vector<tr> a;
set<pair<ll, int>> st, x[N * 4], y[N * 4];
bool del[N];

void ins(int pos, pair<ll, int> val, bool ok, int v = 1, int tl = 1, int tr = s) {
    // cout << tl << ' ' << tr << ' ' << ok << '\n';
    if(ok) {
        x[v].insert(val);
    } else {
        y[v].insert(val);
    }
    if(tl == tr) return;
    int tm = (tl + tr) >> 1;
    if(pos <= tm) ins(pos, val, ok, v + v, tl, tm);
    else ins(pos, val, ok, v + v + 1, tm + 1, tr);
}
int pos[N];
void upd(int l, int r, ll val, ll cost, bool ok, int v = 1, int tl = 1, int tr = s) {
    if(l >  r || tl > r || l > tr) return;
    if(tl >= l && tr <= r) {
        if(ok) {
            while(!x[v].empty()) {
                auto [f, i] = (*x[v].begin());
                if(f > val) break;
                x[v].erase({f, i});
                if(!del[i]) {
                    del[i] = 1;
                    st.insert({cost + a[i].c, i});
                }
            }
        } else {
            while(!y[v].empty()) {
                auto [f, i] = (*y[v].begin());
                if(f > val) break;
                y[v].erase({f, i});
                if(!del[i]) {
                    del[i] = 1;
                    st.insert({cost + a[i].c, i});
                }
            }
        }
    } else {
        int tm = (tl + tr) >> 1;
        upd(l, r, val, cost, ok, v + v, tl, tm);
        upd(l, r, val, cost, ok, v + v + 1, tm + 1, tr);
    }
}
void test() {
    cin >> n >> m;
    a.resize(m);
    for(int i = 0; i < m; i++) {
        d[i] = inf;
        cin >> a[i].t >> a[i].l >> a[i].r >> a[i].c;
        T.push_back(a[i].t);
    }
    sort(T.begin(), T.end());
    T.resize(unique(T.begin(), T.end()) - T.begin());
    s = (int)T.size();
    for(int i = 0; i < m; i++) {
        int j = lower_bound(T.begin(), T.end(), a[i].t) - T.begin() + 1;
        pos[i] = j;
        if(a[i].l == 1) {
            del[i] = 1;
            st.insert({a[i].c, i});
        } else {
            ins(j, {a[i].l - a[i].t, i}, 1);
            ins(j, {a[i].l + a[i].t, i}, 0);
        }
    }

    while(!st.empty()) {
        auto [w, v] = (*st.begin());
        d[v] = w;
        st.erase(st.begin());
        int j = pos[v];
        upd(1, j, a[v].r - a[v].t + 1, d[v], 1);
        upd(j, s, a[v].r + a[v].t + 1, d[v], 0);
    }

    for(int i = 0; i < m; i++) {
        if(a[i].r == n) {
            res = min(res, d[i]);
        }
    }
    if(res == inf) {
        res = -1;
    }
    cout << res << '\n';
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); 
    
    int t = 1; 
    // cin >> t;
    
    while(t--) 
        test();
    
    return 0;
}

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