oj.uz

Submission #941149

# Submission time Handle Problem Language Result Execution time Memory
941149 2024-03-08T08:02:24 Z guagua0407 Treatment Project (JOI20_treatment) C++17
4 / 100
 106 ms 17100 KB 
//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};

void setIO(string s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}

const int mxn=1e5+5;
const ll inf=1e18;
vector<ll> segtree(mxn*4,inf);

void update(int pos,int val,int l=0,int r=mxn-1,int v=1){
    if(l==r){
        segtree[v]=min(segtree[v],val);
        return;
    }
    int mid=(l+r)/2;
    if(pos<=mid) update(pos,val,l,mid,v*2);
    else update(pos,val,mid+1,r,v*2+1);
    segtree[v]=min(segtree[v*2],segtree[v*2+1]);
}

int query(int tl,int tr,int l=0,int r=mxn-1,int v=1){
    if(r<tl or tr<l){
        return inf;
    }
    if(tl<=l and r<=tr){
        return segtree[v];
    }
    int mid=(l+r)/2;
    return min(query(tl,min(mid,tr),l,mid,v*2),query(max(mid+1,tl),tr,mid+1,r,v*2+1));
}

signed main() {_
    int n,m;
    cin>>n>>m;
    vector<int> q[mxn];
    vector<int> t(m),l(m),r(m),c(m);
    vector<int> xs;
    xs.push_back(0);
    for(int i=0;i<m;i++){
        cin>>t[i]>>l[i]>>r[i]>>c[i];
        xs.push_back(r[i]);
    }
    //return 0;
    sort(all(xs));
    xs.resize(unique(all(xs))-xs.begin());
    if(xs.back()!=n){
        cout<<-1<<'\n';
        return 0;
    }
    //return 0;
    for(int i=0;i<m;i++){
        r[i]=lower_bound(all(xs),r[i])-xs.begin();
        q[r[i]].push_back(i);
    }
    //return 0;
    vector<ll> dp(xs.size(),inf);
    update(0,0);
    for(int i=1;i<xs.size();i++){
        for(auto v:q[i]){
            l[v]=lower_bound(all(xs),l[v]-1)-xs.begin();
            dp[i]=min(dp[i],query(l[v],i)+c[v]);
        }
        update(i,dp[i]);
    }
    ll ans=dp[xs.size()-1];
    cout<<(ans==inf?-1:ans)<<'\n';
    return 0;
}
//maybe its multiset not set
//yeeorz
//laborz

// dp[i]=

Compilation message

treatment.cpp: In function 'int main()':
treatment.cpp:72:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |     for(int i=1;i<xs.size();i++){
      |                 ~^~~~~~~~~~
treatment.cpp: In function 'void setIO(std::string)':
treatment.cpp:16:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |     freopen((s + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
treatment.cpp:17:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |     freopen((s + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 17100 KB Output is correct
2 Correct 93 ms 16944 KB Output is correct
3 Correct 69 ms 14284 KB Output is correct
4 Correct 70 ms 14168 KB Output is correct
5 Correct 46 ms 13768 KB Output is correct
6 Correct 48 ms 13764 KB Output is correct
7 Correct 54 ms 14284 KB Output is correct
8 Correct 45 ms 13776 KB Output is correct
9 Correct 48 ms 13832 KB Output is correct
10 Correct 57 ms 14416 KB Output is correct
11 Correct 87 ms 15308 KB Output is correct
12 Correct 83 ms 15308 KB Output is correct
13 Correct 104 ms 16844 KB Output is correct
14 Correct 106 ms 16860 KB Output is correct
15 Correct 90 ms 16956 KB Output is correct
16 Correct 88 ms 16856 KB Output is correct
17 Correct 84 ms 16080 KB Output is correct
18 Correct 79 ms 14580 KB Output is correct

Subtask #2
0 / 5.0

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

Subtask #3
0 / 30.0

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

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 17100 KB Output is correct
2 Correct 93 ms 16944 KB Output is correct
3 Correct 69 ms 14284 KB Output is correct
4 Correct 70 ms 14168 KB Output is correct
5 Correct 46 ms 13768 KB Output is correct
6 Correct 48 ms 13764 KB Output is correct
7 Correct 54 ms 14284 KB Output is correct
8 Correct 45 ms 13776 KB Output is correct
9 Correct 48 ms 13832 KB Output is correct
10 Correct 57 ms 14416 KB Output is correct
11 Correct 87 ms 15308 KB Output is correct
12 Correct 83 ms 15308 KB Output is correct
13 Correct 104 ms 16844 KB Output is correct
14 Correct 106 ms 16860 KB Output is correct
15 Correct 90 ms 16956 KB Output is correct
16 Correct 88 ms 16856 KB Output is correct
17 Correct 84 ms 16080 KB Output is correct
18 Correct 79 ms 14580 KB Output is correct
19 Correct 2 ms 5724 KB Output is correct
20 Incorrect 2 ms 5724 KB Output isn't correct
21 Halted 0 ms 0 KB -