oj.uz

Submission #295196

# Submission time Handle Problem Language Result Execution time Memory
295196 2020-09-09T14:15:33 Z 최은수(#5799) Treatment Project (JOI20_treatment) C++17
0 / 100
 100 ms 7540 KB 
#include<iostream>
#include<vector>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+7;
const ll INF=1e18;
const int mx=100010;
struct fen
{
    ll t[mx*2];
    fen(){fill(t,t+mx*2,INF);}
    inline void upd(int x,ll p)
    {
        for(x=mx*2-10-x;x<mx*2;x+=x&-x)
            t[x]=min(t[x],p);
        return;
    }
    inline ll query(int x)
    {
        ll ret=INF;
        for(x=mx*2-10-x;x>0;x^=x&-x)
            ret=min(ret,t[x]);
        return ret;
    }
}ft;
struct query
{
    int t,l,r,c;
    bool operator<(const query&x)const
    {
        return l<x.l;
    }
};
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin>>n>>m;
    vector<query>qv(m);
    vector<int>cpv;
    for(auto&t:qv)
        cin>>t.t>>t.l>>t.r>>t.c,cpv.eb(t.l),cpv.eb(t.r+1);
    cpv.eb(1);
    cpv.eb(n+1);
    sort(all(cpv)),cpv.erase(unique(all(cpv)),cpv.end());
    for(auto&t:qv)
        t.l=upper_bound(all(cpv),t.l)-cpv.begin(),
        t.r=upper_bound(all(cpv),t.r+1)-cpv.begin()-1;
    sort(all(qv));
    ft.upd(0,0);
    for(auto&t:qv)
        ft.upd(t.r,ft.query(t.l-1)+t.c);
    cout<<ft.query((int)cpv.size()-1)<<endl;
    return 0;
}

Subtask #1
0 / 4.0

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

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1920 KB Output is correct
2 Incorrect 1 ms 1920 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 1920 KB Output is correct
2 Incorrect 1 ms 1920 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 61.0

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