Submission #424636

#	Time	Username	Problem	Language	Result	Execution time	Memory
424636		lyc	Treatment Project (JOI20_treatment)	C++14	100 / 100	470 ms	108160 KiB

treatment

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

#define TRACE(x) cerr << #x << " :: " << x << endl
#define _ << " " <<
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef pair<ll,ll> pll;

const int mxM = 100001;

int N, M;
struct Treat {
    int T, L, R, C;
} treat[mxM];

bool vis[mxM];
vector<ll> vals;
priority_queue<pll,vector<pll>,greater<pll>> pq;

struct node {
    int s, e, m;
    vector<pll> v;
    node *l, *r;
    node(int s, int e): s(s), e(e), m((s+e)/2) {
        if (s != e) {
            l = new node(s,m);
            r = new node(m+1,e);
        }
    }

    void update(int a, pll b) {
        if (s == e) v.push_back(b);
        else if (a <= m) l->update(a,b);
        else r->update(a,b);
    }

    void build() {
        if (s == e) {
            sort(v.rbegin(),v.rend());
        } else {
            l->build();
            r->build();
            auto& a = l->v, b = r->v;
            for (int i = 0, j = 0; i < SZ(a) || j < SZ(b);) {
                if (i < SZ(a) && (j == SZ(b) || a[i] > b[j]))
                    v.push_back(a[i++]);
                else
                    v.push_back(b[j++]);
            }
        }
        //cout << s _ e << ": ";
        //for (auto& x : v) { cout << x.first _ x.second << ", "; } cout << endl;
    }

    void proc(int a, int b, ll x, ll w) {
        if (a > b) return;
        if (a <= s && e <= b) {
            while (SZ(v) && v.back().first <= x) {
                auto i = v.back().second; v.pop_back();
                if (vis[i]) continue;
                vis[i] = 1;
                //cout << "PUSH" _ vals[treat[i].T] _ treat[i].L _ treat[i].R << endl;
                pq.push(pll(w + treat[i].C, i));
            }
        } else {
            if (a <= m) l->proc(a,b,x,w);
            if (b > m) r->proc(a,b,x,w);
        }
    }
} *root1, *root2;

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> N >> M;
    FOR(i,1,M){
        int T, L, R, C;
        cin >> T >> L >> R >> C;
        treat[i] = {T,L,R,C};
        vals.push_back(T);
    }
    sort(ALL(vals));
    vals.resize(unique(ALL(vals))-vals.begin());

    root1 = new node(0,SZ(vals)-1);
    root2 = new node(0,SZ(vals)-1);

    memset(vis,0,sizeof vis);

    FOR(i,1,M){
        auto& t = treat[i];
        t.T = lower_bound(ALL(vals),t.T)-vals.begin();

        //cout << i _ t.T _ t.L+vals[t.T]-1 _ t.L-vals[t.T]-1 << endl;
        //cout << i _ t.T _ t.R+vals[t.T] _ t.R-vals[t.T]-1 << endl;
        if (t.L == 1) {
            vis[i] = 1;
            pq.push(pll(t.C,i));
        } else {
            root1->update(t.T, pll(t.L+vals[t.T]-1,i));
            root2->update(t.T, pll(t.L-vals[t.T]-1,i));
        }
    }

    root1->build();
    root2->build();

    while (!pq.empty()) {
        auto [w, u] = pq.top(); pq.pop();
        auto t = treat[u];
        //TRACE(u _ vals[t.T] _ t.L _ t.R _ w);
        if (t.R == N) {
            cout << w << '\n';
            return 0;
        }

        root1->proc(t.T, SZ(vals)-1, t.R+vals[t.T], w);
        root2->proc(0, t.T-1, t.R-vals[t.T], w);
    }

    cout << -1 << '\n';
}

Compilation message (stderr)

treatment.cpp: In function 'int main()':
treatment.cpp:113:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  113 |         auto [w, u] = pq.top(); pq.pop();
      |              ^

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