oj.uz

Submission #423938

# Submission time Handle Problem Language Result Execution time Memory
423938 2021-06-11T14:17:45 Z tqbfjotld Treatment Project (JOI20_treatment) C++14
4 / 100
 142 ms 17740 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long

int memo[100005];
vector<pair<pair<int,int>,pair<int,int> > > stuff;
bool cmp(pair<pair<int,int>,pair<int,int>> a, pair<pair<int,int>,pair<int,int>> b){
    return a.second.first-a.first.first<b.second.first-b.first.first;
}
int T[100005];
int L[100005];
int R[100005];
int C[100005];
int R_T[100005];

struct node{
    int s,e,v;
    node *l,*r;
    node (int _s, int _e){
        s = _s; e = _e;
        v = 999999999999999999LL;
        if (s!=e){
            l = new node(s,(s+e)/2);
            r = new node((s+e)/2+1,e);
        }
    }
    void upd(int pos, int val){
        if (s==e){
            v = val;
            return;
        }
        if (pos<=(s+e)/2) l->upd(pos,val);
        else r->upd(pos,val);
        v = min(l->v,r->v);
        return ;
    }
    int qu(int a, int b){
        if (a<=s && e<=b) return v;
        if (b<=(s+e)/2) return l->qu(a,b);
        if (a>(s+e)/2) return r->qu(a,b);
        return min(l->qu(a,b),r->qu(a,b));
    }
}*root;

main(){
    int n,m;
    scanf("%lld%lld",&n,&m);
    root = new node(0,m);
    for (int x = 0; x<m; x++){
        int t,l,r,c;
        scanf("%lld%lld%lld%lld",&t,&l,&r,&c);
        stuff.push_back({{t,l},{r,c}});
    }
    sort(stuff.begin(),stuff.end(),cmp);
    for (int x = 0; x<m; x++){
        T[x] = stuff[x].first.first;
        L[x] = stuff[x].first.second;
        R[x] = stuff[x].second.first;
        C[x] = stuff[x].second.second;
        R_T[x] = R[x];
    }
    int ans = 999999999999999999LL;
    for (int x = 0; x<m; x++){
        if (L[x]==1){
            memo[x] = C[x];
            root->upd(x,C[x]);
            continue;
        }
        memo[x] = C[x];
        int minv = lower_bound(R_T,R_T+m,L[x]-1)-R_T;
        memo[x] += root->qu(minv,x);
        memo[x] = min(memo[x],999999999999999999LL);
        root->upd(x,memo[x]);
    }
    for (int x = 0; x<m; x++){
        if (R[x]==n){
            ans = min(ans,memo[x]);
        }
        //printf("memo %lld = %lld\n",x,memo[x]);
    }
    printf("%lld",ans==999999999999999999LL?-1LL:ans);
}

Compilation message

treatment.cpp:45:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   45 | main(){
      | ^~~~
treatment.cpp: In function 'int main()':
treatment.cpp:47:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |     scanf("%lld%lld",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~~~~
treatment.cpp:51:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |         scanf("%lld%lld%lld%lld",&t,&l,&r,&c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 17576 KB Output is correct
2 Correct 108 ms 17600 KB Output is correct
3 Correct 118 ms 17540 KB Output is correct
4 Correct 136 ms 17556 KB Output is correct
5 Correct 142 ms 17600 KB Output is correct
6 Correct 97 ms 17600 KB Output is correct
7 Correct 110 ms 17576 KB Output is correct
8 Correct 96 ms 17560 KB Output is correct
9 Correct 96 ms 17552 KB Output is correct
10 Correct 100 ms 17608 KB Output is correct
11 Correct 134 ms 17564 KB Output is correct
12 Correct 139 ms 17564 KB Output is correct
13 Correct 120 ms 17576 KB Output is correct
14 Correct 125 ms 17740 KB Output is correct
15 Correct 111 ms 17604 KB Output is correct
16 Correct 109 ms 17576 KB Output is correct
17 Correct 111 ms 17576 KB Output is correct
18 Correct 128 ms 17628 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Incorrect 0 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Incorrect 0 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 17576 KB Output is correct
2 Correct 108 ms 17600 KB Output is correct
3 Correct 118 ms 17540 KB Output is correct
4 Correct 136 ms 17556 KB Output is correct
5 Correct 142 ms 17600 KB Output is correct
6 Correct 97 ms 17600 KB Output is correct
7 Correct 110 ms 17576 KB Output is correct
8 Correct 96 ms 17560 KB Output is correct
9 Correct 96 ms 17552 KB Output is correct
10 Correct 100 ms 17608 KB Output is correct
11 Correct 134 ms 17564 KB Output is correct
12 Correct 139 ms 17564 KB Output is correct
13 Correct 120 ms 17576 KB Output is correct
14 Correct 125 ms 17740 KB Output is correct
15 Correct 111 ms 17604 KB Output is correct
16 Correct 109 ms 17576 KB Output is correct
17 Correct 111 ms 17576 KB Output is correct
18 Correct 128 ms 17628 KB Output is correct
19 Correct 0 ms 204 KB Output is correct
20 Incorrect 0 ms 332 KB Output isn't correct
21 Halted 0 ms 0 KB -