oj.uz

Submission #360120

# Submission time Handle Problem Language Result Execution time Memory
360120 2021-01-27T13:25:21 Z teehandsome Fuel Station (NOI20_fuelstation) C++11
24 / 100
 194 ms 42768 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define endl '\n'
#define INF 1e9+7
#define all(x) x.begin(),x.end()
using namespace std;
using namespace __gnu_pbds;
using ll=long long;
using pii=pair<int,int>;
using ppi=pair<int,pii>;
using oset=tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>;

template<typename T>
void _print(vector<T> x) {cerr<<"{"; for(auto e:x) cerr<<e<<","; cerr<<"}";}
void _print(pii x) {cerr<<"{"<<x.first<<","<<x.second<<"}";}
template<typename T>
void _print(T x) {cerr<<x;}

void dbg() {cerr<<endl;}
template<typename Head,typename... Tail>
void dbg(Head H,Tail... T) {
    _print(H);
    if(sizeof...(T)) cerr<<",";
    else cerr<<"\"]";
    dbg(T...);
}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:[\"",dbg(__VA_ARGS__)

const int mxn=3e5+10;
int n,d;
//map<int,vector<int>> ar;
vector<int> ar[mxn];
struct dt {
    int x,a,b;
    bool operator<(const dt &r) {return x<r.x;}
};
vector<dt> s;
vector<int> B;
int t[3*mxn],lazy[3*mxn];
ll sum[mxn];
ll ans=INF;

void push(int x) {
    t[2*x]+=lazy[x];
    t[2*x+1]+=lazy[x];
    lazy[2*x]+=lazy[x];
    lazy[2*x+1]+=lazy[x];
    lazy[x]=0;
}

void build(int v,int tl,int tr) {
    if(tl==tr) {
        t[v]=-s[tl].x;
        if(tl) t[v]+=sum[tl-1];
    }
    else {
        int mid=(tl+tr)/2;
        build(2*v,tl,mid);
        build(2*v+1,mid+1,tr);
        t[v]=min(t[2*v],t[2*v+1]);
    }
}
void add(int v,int tl,int tr,int l,int r,int val) {
    if(tl>tr or tl>r or tr<l) return;
    if(tl>=l and tr<=r) {
        t[v]+=val;
        lazy[v]+=val;
    }
    else {
        push(v);
        int mid=(tl+tr)/2;
        add(2*v,tl,mid,l,r,val);
        add(2*v+1,mid+1,tr,l,r,val);
        t[v]=min(t[2*v],t[2*v+1]);
    }
}
int query(int v,int tl,int tr,int l,int r) {
    if(l>r or l>tr or r<tl) return INF;
    if(tl>=l and tr<=r) {
        return t[v];
    }
    else {
        push(v);
        int mid=(tl+tr)/2;
        return min(query(2*v,tl,mid,l,r),query(2*v+1,mid+1,tr,l,r));
    }
}

int main () {
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>n>>d; int N=n+1;
    for(int i=0;i<n;i++) {
        int x,a,b; cin>>x>>a>>b;
        s.push_back({x,a,b}); B.push_back(b);
    }
    s.push_back({d,0,d}); B.push_back(d);
    sort(all(s));
    sort(all(B)); B.erase(unique(all(B)),end(B));
    for(int i=0;i<N;i++) {
        sum[i]=s[i].a;
        if(i) sum[i]+=sum[i-1];
    }

    for(int i=0;i<N;i++) {
        //ar[s[i].b].push_back(i);
        int pos=lower_bound(all(B),s[i].b)-begin(B);
        ar[pos].push_back(i);
    }
    build(1,0,N-1);
    int past=-1;
    int cnt=0;
    for(auto e:B) {
        if(past==-1) add(1,0,N-1,0,N-1,e);
        else add(1,0,N-1,0,N-1,e-past);
        int res=query(1,0,N-1,0,N-1);
        //debug(res);
        if(res>=0) {
            cout<<e-res<<endl; return 0;
        }
        for(int u:ar[cnt]) {
            add(1,0,N-1,u+1,N-1,-s[u].a);
        }
        past=e; cnt++;
    }
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7404 KB Output is correct
2 Correct 5 ms 7404 KB Output is correct
3 Correct 5 ms 7404 KB Output is correct
4 Correct 5 ms 7404 KB Output is correct
5 Correct 5 ms 7404 KB Output is correct
6 Correct 5 ms 7404 KB Output is correct
7 Correct 5 ms 7404 KB Output is correct
8 Correct 5 ms 7404 KB Output is correct
9 Correct 6 ms 7404 KB Output is correct
10 Correct 6 ms 7404 KB Output is correct
11 Correct 6 ms 7404 KB Output is correct
12 Correct 5 ms 7404 KB Output is correct
13 Correct 6 ms 7404 KB Output is correct
14 Correct 6 ms 7404 KB Output is correct
15 Correct 6 ms 7404 KB Output is correct

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 188 ms 42768 KB Execution killed with signal 7
2 Halted 0 ms 0 KB -

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7552 KB Output is correct
2 Correct 10 ms 7916 KB Output is correct
3 Correct 11 ms 7916 KB Output is correct
4 Correct 11 ms 7916 KB Output is correct
5 Correct 10 ms 7916 KB Output is correct
6 Correct 11 ms 8044 KB Output is correct
7 Correct 11 ms 8044 KB Output is correct
8 Correct 5 ms 7404 KB Output is correct
9 Correct 5 ms 7404 KB Output is correct
10 Correct 5 ms 7404 KB Output is correct
11 Correct 5 ms 7404 KB Output is correct
12 Correct 6 ms 7416 KB Output is correct
13 Correct 5 ms 7404 KB Output is correct
14 Correct 14 ms 8052 KB Output is correct
15 Correct 14 ms 8052 KB Output is correct
16 Correct 14 ms 8044 KB Output is correct
17 Correct 14 ms 8044 KB Output is correct
18 Correct 17 ms 8044 KB Output is correct
19 Correct 10 ms 8044 KB Output is correct
20 Correct 11 ms 7916 KB Output is correct
21 Correct 10 ms 7916 KB Output is correct
22 Correct 10 ms 7916 KB Output is correct
23 Correct 9 ms 7916 KB Output is correct
24 Correct 10 ms 7916 KB Output is correct
25 Correct 9 ms 7916 KB Output is correct

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7552 KB Output is correct
2 Correct 10 ms 7916 KB Output is correct
3 Correct 11 ms 7916 KB Output is correct
4 Correct 11 ms 7916 KB Output is correct
5 Correct 10 ms 7916 KB Output is correct
6 Correct 11 ms 8044 KB Output is correct
7 Correct 11 ms 8044 KB Output is correct
8 Correct 5 ms 7404 KB Output is correct
9 Correct 5 ms 7404 KB Output is correct
10 Correct 5 ms 7404 KB Output is correct
11 Correct 5 ms 7404 KB Output is correct
12 Correct 6 ms 7416 KB Output is correct
13 Correct 5 ms 7404 KB Output is correct
14 Correct 14 ms 8052 KB Output is correct
15 Correct 14 ms 8052 KB Output is correct
16 Correct 14 ms 8044 KB Output is correct
17 Correct 14 ms 8044 KB Output is correct
18 Correct 17 ms 8044 KB Output is correct
19 Correct 10 ms 8044 KB Output is correct
20 Correct 11 ms 7916 KB Output is correct
21 Correct 10 ms 7916 KB Output is correct
22 Correct 10 ms 7916 KB Output is correct
23 Correct 9 ms 7916 KB Output is correct
24 Correct 10 ms 7916 KB Output is correct
25 Correct 9 ms 7916 KB Output is correct
26 Correct 50 ms 7368 KB Output is correct
27 Runtime error 194 ms 41220 KB Execution killed with signal 7
28 Halted 0 ms 0 KB -

Subtask #5
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7404 KB Output is correct
2 Correct 5 ms 7404 KB Output is correct
3 Correct 5 ms 7404 KB Output is correct
4 Correct 5 ms 7404 KB Output is correct
5 Correct 5 ms 7404 KB Output is correct
6 Correct 5 ms 7404 KB Output is correct
7 Correct 5 ms 7404 KB Output is correct
8 Correct 5 ms 7404 KB Output is correct
9 Correct 6 ms 7404 KB Output is correct
10 Correct 6 ms 7404 KB Output is correct
11 Correct 6 ms 7404 KB Output is correct
12 Correct 5 ms 7404 KB Output is correct
13 Correct 6 ms 7404 KB Output is correct
14 Correct 6 ms 7404 KB Output is correct
15 Correct 6 ms 7404 KB Output is correct
16 Correct 5 ms 7404 KB Output is correct
17 Correct 49 ms 7404 KB Output is correct
18 Correct 7 ms 7548 KB Output is correct
19 Correct 5 ms 7404 KB Output is correct
20 Correct 6 ms 7404 KB Output is correct
21 Correct 6 ms 7404 KB Output is correct
22 Correct 6 ms 7404 KB Output is correct
23 Correct 6 ms 7404 KB Output is correct
24 Correct 49 ms 7444 KB Output is correct
25 Incorrect 5 ms 7404 KB Output isn't correct
26 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7404 KB Output is correct
2 Correct 5 ms 7404 KB Output is correct
3 Correct 5 ms 7404 KB Output is correct
4 Correct 5 ms 7404 KB Output is correct
5 Correct 5 ms 7404 KB Output is correct
6 Correct 5 ms 7404 KB Output is correct
7 Correct 5 ms 7404 KB Output is correct
8 Correct 5 ms 7404 KB Output is correct
9 Correct 6 ms 7404 KB Output is correct
10 Correct 6 ms 7404 KB Output is correct
11 Correct 6 ms 7404 KB Output is correct
12 Correct 5 ms 7404 KB Output is correct
13 Correct 6 ms 7404 KB Output is correct
14 Correct 6 ms 7404 KB Output is correct
15 Correct 6 ms 7404 KB Output is correct
16 Correct 6 ms 7552 KB Output is correct
17 Correct 10 ms 7916 KB Output is correct
18 Correct 11 ms 7916 KB Output is correct
19 Correct 11 ms 7916 KB Output is correct
20 Correct 10 ms 7916 KB Output is correct
21 Correct 11 ms 8044 KB Output is correct
22 Correct 11 ms 8044 KB Output is correct
23 Correct 5 ms 7404 KB Output is correct
24 Correct 5 ms 7404 KB Output is correct
25 Correct 5 ms 7404 KB Output is correct
26 Correct 5 ms 7404 KB Output is correct
27 Correct 6 ms 7416 KB Output is correct
28 Correct 5 ms 7404 KB Output is correct
29 Correct 14 ms 8052 KB Output is correct
30 Correct 14 ms 8052 KB Output is correct
31 Correct 14 ms 8044 KB Output is correct
32 Correct 14 ms 8044 KB Output is correct
33 Correct 17 ms 8044 KB Output is correct
34 Correct 10 ms 8044 KB Output is correct
35 Correct 11 ms 7916 KB Output is correct
36 Correct 10 ms 7916 KB Output is correct
37 Correct 10 ms 7916 KB Output is correct
38 Correct 9 ms 7916 KB Output is correct
39 Correct 10 ms 7916 KB Output is correct
40 Correct 9 ms 7916 KB Output is correct
41 Correct 5 ms 7552 KB Output is correct
42 Correct 14 ms 8044 KB Output is correct
43 Correct 17 ms 8180 KB Output is correct
44 Incorrect 16 ms 8204 KB Output isn't correct
45 Halted 0 ms 0 KB -

Subtask #7
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7404 KB Output is correct
2 Correct 5 ms 7404 KB Output is correct
3 Correct 5 ms 7404 KB Output is correct
4 Correct 5 ms 7404 KB Output is correct
5 Correct 5 ms 7404 KB Output is correct
6 Correct 5 ms 7404 KB Output is correct
7 Correct 5 ms 7404 KB Output is correct
8 Correct 5 ms 7404 KB Output is correct
9 Correct 6 ms 7404 KB Output is correct
10 Correct 6 ms 7404 KB Output is correct
11 Correct 6 ms 7404 KB Output is correct
12 Correct 5 ms 7404 KB Output is correct
13 Correct 6 ms 7404 KB Output is correct
14 Correct 6 ms 7404 KB Output is correct
15 Correct 6 ms 7404 KB Output is correct
16 Runtime error 188 ms 42768 KB Execution killed with signal 7
17 Halted 0 ms 0 KB -