oj.uz

Submission #1046996

# Submission time Handle Problem Language Result Execution time Memory
1046996 2024-08-07T07:27:06 Z 변재우(#11026) Treatment Project (JOI20_treatment) C++17
4 / 100
 526 ms 404692 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.r<b.r;});
    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;
}

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

// const int Nmax=100010, INF=1e18;
// int N, M, ans=INF, D[Nmax];
// struct Data {
//     int t, l, r, c;
// }A[Nmax];

// 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++;
//     }
//     sort(A+1, A+M+1, [](Data a, Data b) {return a.l<b.l;});
//     fill(D+1, D+M+1, INF);
//     for(int i=1; i<=M; i++) {
//         if(A[i].l==1) D[i]=A[i].c;
//         else {
//             for(int j=1; j<i; j++) if()
//         }
//     }
//     if(ans==INF) cout<<-1;
//     else cout<<ans;
//     return 0;
// }

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 526 ms 404692 KB Output is correct
2 Correct 494 ms 404660 KB Output is correct
3 Correct 356 ms 166840 KB Output is correct
4 Correct 325 ms 166748 KB Output is correct
5 Correct 186 ms 48056 KB Output is correct
6 Correct 202 ms 51132 KB Output is correct
7 Correct 249 ms 83288 KB Output is correct
8 Correct 196 ms 47980 KB Output is correct
9 Correct 205 ms 51128 KB Output is correct
10 Correct 242 ms 83212 KB Output is correct
11 Correct 415 ms 226068 KB Output is correct
12 Correct 401 ms 225420 KB Output is correct
13 Correct 513 ms 402616 KB Output is correct
14 Correct 496 ms 402616 KB Output is correct
15 Correct 479 ms 404404 KB Output is correct
16 Correct 499 ms 403940 KB Output is correct
17 Correct 498 ms 404408 KB Output is correct
18 Correct 392 ms 225204 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 41560 KB Output is correct
2 Incorrect 21 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 20 ms 41560 KB Output is correct
2 Incorrect 21 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 526 ms 404692 KB Output is correct
2 Correct 494 ms 404660 KB Output is correct
3 Correct 356 ms 166840 KB Output is correct
4 Correct 325 ms 166748 KB Output is correct
5 Correct 186 ms 48056 KB Output is correct
6 Correct 202 ms 51132 KB Output is correct
7 Correct 249 ms 83288 KB Output is correct
8 Correct 196 ms 47980 KB Output is correct
9 Correct 205 ms 51128 KB Output is correct
10 Correct 242 ms 83212 KB Output is correct
11 Correct 415 ms 226068 KB Output is correct
12 Correct 401 ms 225420 KB Output is correct
13 Correct 513 ms 402616 KB Output is correct
14 Correct 496 ms 402616 KB Output is correct
15 Correct 479 ms 404404 KB Output is correct
16 Correct 499 ms 403940 KB Output is correct
17 Correct 498 ms 404408 KB Output is correct
18 Correct 392 ms 225204 KB Output is correct
19 Correct 20 ms 41560 KB Output is correct
20 Incorrect 21 ms 41544 KB Output isn't correct
21 Halted 0 ms 0 KB -