oj.uz

Submission #1046989

# Submission time Handle Problem Language Result Execution time Memory
1046989 2024-08-07T07:23:39 Z 변재우(#11026) Treatment Project (JOI20_treatment) C++17
4 / 100
 591 ms 404684 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int Nmax=100010, INF=1e18, S=(1<<18);
int N, M, ans=INF, D[Nmax];
struct Data {
    int t, l, r, c;
}A[Nmax];
vector<int> T, X;

struct Seg2D {
    struct Seg1D {
        struct Node {
            int v; Node *l, *r;
            Node() {v=INF, l=r=NULL;}
        };
        Node *root;
        Seg1D() {root=new Node();}
        void Update(int k, int v) {Update(root, 1, S, k, v);}
        int Query(int l, int r) {return Query(root, 1, S, l, r);}
        void Update(Node *curr, int s, int e, int k, int v) {
            curr->v=min(curr->v, v);
            if(s==e) return;
            int m=(s+e)/2;
            if(k<=m) {
                if(!(curr->l)) curr->l=new Node();
                Update(curr->l, s, m, k, v);
            }
            else {
                if(!(curr->r)) curr->r=new Node();
                Update(curr->r, m+1, e, k, v);
            }
        }
        int Query(Node *curr, int s, int e, int l, int r) {
            if(!curr || s>r || l>e) return INF;
            if(l<=s && e<=r) return curr->v;
            int m=(s+e)/2;
            return min(Query(curr->l, s, m, l, r), Query(curr->r, m+1, e, l, r));
        }
    }Tree[2*S];
    void Update(int k, int x, int v) {Update(1, 1, S, k, x, v);}
    void Update(int node, int s, int e, int k, int x, int v) {
        Tree[node].Update(x, v);
        if(s==e) return;
        int lch=2*node, rch=lch+1, m=(s+e)/2;
        if(k<=m) Update(lch, s, m, k, x, v);
        else Update(rch, m+1, e, k, x, v);
    }
    int Query(int l, int r, int lo, int hi) {return Query(1, 1, S, l, r, lo, hi);}
    int Query(int node, int s, int e, int l, int r, int lo, int hi) {
        if(s>r || l>e) return INF;
        if(l<=s && e<=r) return Tree[node].Query(lo, hi);
        int lch=2*node, rch=lch+1, m=(s+e)/2;
        return min(Query(lch, s, m, l, r, lo, hi), Query(rch, m+1, e, l, r, lo, hi));
    }
}P, P2;

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>N>>M;
    for(int i=1; i<=M; i++) {
        cin>>A[i].t>>A[i].l>>A[i].r>>A[i].c;
        A[i].r++;
        T.push_back(A[i].t);
        X.push_back(A[i].r-A[i].t), X.push_back(A[i].r+A[i].t);
    }
    sort(A+1, A+M+1, [](Data a, Data b) {return a.l<b.l;});
    sort(T.begin(), T.end()), T.erase(unique(T.begin(), T.end()), T.end());
    sort(X.begin(), X.end()), X.erase(unique(X.begin(), X.end()), X.end());
    fill(D+1, D+M+1, INF);
    for(int i=1; i<=M; i++) {
        //cout<<i<<": "<<A[i].l<<"~"<<A[i].r<<": "<<A[i].t<<", "<<A[i].c<<"\n";
        if(A[i].l==1) D[i]=A[i].c;
        else {
            //cout<<"aa"<<1<<"~"<<lower_bound(T.begin(), T.end(), A[i].t)-T.begin()+1<<", "<<lower_bound(X.begin(), X.end(), A[i].l+A[i].t)-X.begin()+1<<"~"<<X.size()<<"\n";
            int a=P.Query(1, lower_bound(T.begin(), T.end(), A[i].t)-T.begin()+1, lower_bound(X.begin(), X.end(), A[i].l+A[i].t)-X.begin()+1, X.size());
            int b=P2.Query(lower_bound(T.begin(), T.end(), A[i].t)-T.begin()+1, T.size(), lower_bound(X.begin(), X.end(), A[i].l-A[i].t)-X.begin()+1, X.size());
            D[i]=min(a, b)+A[i].c;
        }
        if(A[i].r==N+1) ans=min(ans, D[i]);
        //cout<<i<<": "<<D[i]<<"\n";
        //cout<<"aa"<<lower_bound(T.begin(), T.end(), A[i].t)-T.begin()+1<<", "<<lower_bound(X.begin(), X.end(), A[i].r+A[i].t)-X.begin()+1<<": "<<D[i]<<"\n";
        //cout<<"bb"<<lower_bound(T.begin(), T.end(), A[i].t)-T.begin()+1<<", "<<lower_bound(X.begin(), X.end(), A[i].r-A[i].t)-X.begin()+1<<": "<<D[i]<<"\n";
        P.Update(lower_bound(T.begin(), T.end(), A[i].t)-T.begin()+1, lower_bound(X.begin(), X.end(), A[i].r+A[i].t)-X.begin()+1, D[i]);
        P2.Update(lower_bound(T.begin(), T.end(), A[i].t)-T.begin()+1, lower_bound(X.begin(), X.end(), A[i].r-A[i].t)-X.begin()+1, D[i]);
    }
    if(ans==INF) cout<<-1;
    else cout<<ans;
    return 0;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 485 ms 404568 KB Output is correct
2 Correct 504 ms 404684 KB Output is correct
3 Correct 392 ms 166588 KB Output is correct
4 Correct 382 ms 166584 KB Output is correct
5 Correct 193 ms 48060 KB Output is correct
6 Correct 216 ms 51132 KB Output is correct
7 Correct 241 ms 83364 KB Output is correct
8 Correct 189 ms 48060 KB Output is correct
9 Correct 207 ms 51256 KB Output is correct
10 Correct 247 ms 83456 KB Output is correct
11 Correct 531 ms 226232 KB Output is correct
12 Correct 529 ms 225384 KB Output is correct
13 Correct 591 ms 402800 KB Output is correct
14 Correct 580 ms 402736 KB Output is correct
15 Correct 550 ms 404276 KB Output is correct
16 Correct 547 ms 403956 KB Output is correct
17 Correct 539 ms 404412 KB Output is correct
18 Correct 537 ms 225212 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 41560 KB Output is correct
2 Incorrect 24 ms 41544 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 41560 KB Output is correct
2 Incorrect 24 ms 41544 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 485 ms 404568 KB Output is correct
2 Correct 504 ms 404684 KB Output is correct
3 Correct 392 ms 166588 KB Output is correct
4 Correct 382 ms 166584 KB Output is correct
5 Correct 193 ms 48060 KB Output is correct
6 Correct 216 ms 51132 KB Output is correct
7 Correct 241 ms 83364 KB Output is correct
8 Correct 189 ms 48060 KB Output is correct
9 Correct 207 ms 51256 KB Output is correct
10 Correct 247 ms 83456 KB Output is correct
11 Correct 531 ms 226232 KB Output is correct
12 Correct 529 ms 225384 KB Output is correct
13 Correct 591 ms 402800 KB Output is correct
14 Correct 580 ms 402736 KB Output is correct
15 Correct 550 ms 404276 KB Output is correct
16 Correct 547 ms 403956 KB Output is correct
17 Correct 539 ms 404412 KB Output is correct
18 Correct 537 ms 225212 KB Output is correct
19 Correct 28 ms 41560 KB Output is correct
20 Incorrect 24 ms 41544 KB Output isn't correct
21 Halted 0 ms 0 KB -