Submission #534832

#	Time	Username	Problem	Language	Result	Execution time	Memory
534832		qwerasdfzxcl	Treatment Project (JOI20_treatment)	C++14	100 / 100	235 ms	22872 KiB

treatment

#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
constexpr ll INF = 1e18;
constexpr int INF2 = 2e9;
ll dist[100100];
struct Fenwick{
    vector<pair<int, int>> tree[100100];
    int sz;
    void init(int n){sz = n;}
    void init2(){for (int i=0;i<=sz;i++) sort(tree[i].begin(), tree[i].end(), greater<pair<int, int>>());}
    void update(int x, int y, int i){
        while(x<=sz){
            tree[x].emplace_back(y, i);
            x += x&-x;
        }
    }
    pair<int, int> query(int x){
        pair<int, int> ret = {INF2, 0};
        while(x){
            while(!tree[x].empty() && dist[tree[x].back().second]!=INF) tree[x].pop_back();
            if (!tree[x].empty()) ret = min(ret, tree[x].back());
            x -= x&-x;
        }
        return ret;
    }
    int pop(int x, int y){
        auto [val, idx] = query(x);
        if (val>y) return 0;
        return idx;
    }
}tree;
int T[100100], L[100100], R[100100], C[100100];

void compress(vector<int> &v) {sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end());}
inline int getidx(const vector<int> &v, int x) {return lower_bound(v.begin(), v.end(), x) - v.begin();}
inline int getidx2(const vector<int> &v, int x) {return upper_bound(v.begin(), v.end(), x) - v.begin() - 1;}

int main(){
    int X, n;
    scanf("%d %d", &X, &n);

    vector<int> x;
    x.push_back(-INF2);
    for (int i=1;i<=n;i++){
        scanf("%d %d %d %d", T+i, L+i, R+i, C+i);
        x.push_back(L[i] + T[i]);
    }

    compress(x);
    tree.init(n+2);

    fill(dist+1, dist+n+1, INF);
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
    for (int i=1;i<=n;i++){
        tree.update(getidx(x, L[i]+T[i]), L[i]-T[i], i);
        if (L[i]==1){
            dist[i] = C[i];
            pq.emplace(C[i], i);
        }
    }

    tree.init2();

    while(!pq.empty()){
        auto [c, s] = pq.top(); pq.pop();
        int xc = getidx2(x, R[s]+1+T[s]), yc = R[s]+1-T[s], v;
        while(true){
            v = tree.pop(xc, yc);
            if (!v) break;
            dist[v] = c + C[v];
            pq.emplace(dist[v], v);
        }
    }

    ll ans = INF;
    for (int i=1;i<=n;i++) if (R[i]==X) ans = min(ans, dist[i]);
    printf("%lld\n", ans==INF?-1:ans);
    return 0;
}

Compilation message (stderr)

treatment.cpp: In member function 'int Fenwick::pop(int, int)':
treatment.cpp:29:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   29 |         auto [val, idx] = query(x);
      |              ^
treatment.cpp: In function 'int main()':
treatment.cpp:67:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   67 |         auto [c, s] = pq.top(); pq.pop();
      |              ^
treatment.cpp:42:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |     scanf("%d %d", &X, &n);
      |     ~~~~~^~~~~~~~~~~~~~~~~
treatment.cpp:47:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |         scanf("%d %d %d %d", T+i, L+i, R+i, C+i);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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