Submission #380978

#	Time	Username	Problem	Language	Result	Execution time	Memory
380978		PedroBigMan	Fuel Station (NOI20_fuelstation)	C++14	100 / 100	1293 ms	115788 KiB

FuelStation

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <deque>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
#define REP(i,a,b) for(ll i=a; i<b; i++)
#define pb push_back
#define mp make_pair
#define pl pair<ll,ll>
#define ff first
#define ss second
#define INF 100000000000000000LL
ll insig;
#define In(vecBRO, LENBRO) REP(IBRO,0,LENBRO) {cin>>insig; vecBRO.pb(insig);}
void Out(vector<ll> x) {REP(i,0,x.size()) {cout<<x[i]<<" ";} cout<<endl;}

class ST
{
    public:
    ll N; 
    
    class SV //seg value
    {
        public:
        ll a;
        SV() {a=-INF;}
        SV(ll x) {a=x;}
    };
      
    class LV //lazy value
    {
        public:
        ll a;
        LV() {a=0LL;}
        LV(ll x) {a=x;}
    };
    
    SV op(SV A, SV B) //how seg values interact
    {
        SV X(max(A.a,B.a)); 
        return X;
    }
    
    SV upval(ll c, ll x, ll y) //how lazy values modify a seg value, c=current node ,[x,y]=interval acting
    {
        SV X(p[c].a+lazy[c].a);
        return X;
    }
    
    LV inter(LV A,LV B) //how lazy values interact
    {
        LV X(A.a+B.a);
        return X;
    }
    
    SV neuts; LV neutl;
    
    vector<SV> ar; vector<SV> p;
    vector<LV> lazy;
    
    ST(vector<ll> arr)
    {
        N = (ll) 1<<(ll) ceil(log2(arr.size()));
        REP(i,0,arr.size()) {SV X(arr[i]); ar.pb(X);} 
        REP(i,arr.size(),N) {ar.pb(neuts);}
        REP(i,0,N) {p.pb(neuts);}
        REP(i,0,N) {p.pb(ar[i]);}
        ll cur = N-1;
        while(cur>0)
        {
            p[cur]=op(p[2*cur],p[2*cur+1]);
            cur--;
        }
        REP(i,0,2*N) {lazy.pb(neutl);}
    }
    
    void prop(ll c, ll x, ll y) //how lazy values propagate
    {
        p[c]=upval(c,x,y);
        lazy[2*c]=inter(lazy[c],lazy[2*c]); lazy[2*c+1]=inter(lazy[c],lazy[2*c+1]);
        lazy[c]=neutl;
        if(2*c>=N) 
        {
            p[2*c]=upval(2*c,2*c,2*c); p[2*c+1]=upval(2*c+1,2*c+1,2*c+1);
            ar[2*c-N]=p[2*c];
            ar[2*c+1-N]=p[2*c+1];
            lazy[2*c]=neutl; lazy[2*c+1]=neutl;
        }
    }
    
    SV query(ll a,ll b, ll c, ll x, ll y) //c=current node, starting in 1, a,b=range of query, x,y=range of node c in the array down, x,y from 0 to N-1. query(a,b)->query(a,b,1,0,N-1)
    {
        if(y<a || x>b) {return neuts;}
        if(x>=a && y<=b) {return upval(c,x,y);}
        prop(c,x,y);
        ll mid=(x+y)/2;
        SV ans = op(query(a,b,2*c,x,mid),query(a,b,2*c+1,mid+1,y));
        return ans;
    }
    
    void update(LV s, ll a, ll b, ll c, ll x, ll y) //positions in [a,b] from 0 to N-1 gets +s
    {
        if(y<a || x>b) {return ;}
        if(x>=a && y<=b) 
        {
            lazy[c]=inter(s,lazy[c]);  
            if(c>=N) {p[c]=upval(c,c,c); lazy[c]=neutl; ar[c-N]=p[c];}
            return;
        }
        ll mid=(x+y)/2;
        update(s,a,b,2*c,x,mid); update(s,a,b,2*c+1,mid+1,y);
        p[c]=op(upval(2*c,x,mid),upval(2*c+1,mid+1,y));
    }
};

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    ll N,D; cin>>N>>D; vector<ll> xx; xx.pb(0LL); xx.pb(0LL); xx.pb(0LL); vector<vector<ll> > Sta;
    REP(i,0,N) {cin>>xx[0]>>xx[1]>>xx[2]; Sta.pb(xx);}
    sort(Sta.begin(),Sta.end());
    vector<ll> X,A,B; REP(i,0,N) {X.pb(Sta[i][0]); A.pb(Sta[i][1]); B.pb(Sta[i][2]);}
    map<ll,vector<ll> > m; 
    REP(i,0,N)
    {
        m[B[i]].pb(i);
    }
    set<ll> bvals; REP(i,0,N) {bvals.insert(B[i]);}
    vector<ll> Sbeg; ll psA=0LL;
    REP(i,0,N) {Sbeg.pb(X[i]-psA); psA+=A[i];}
    Sbeg.pb(D-psA);
    ST S(Sbeg);
    set<ll>::iterator it=bvals.begin();
    ll ans=D;
    while(it!=bvals.end())
    {
        if(it!=bvals.begin())
        {
            it--;
            REP(i,0,m[*it].size()) 
            {
                ll ind=m[*it][i];
                ST::LV U(A[ind]);
                S.update(U,ind+1LL,S.N-1,1LL,0LL,S.N-1LL);
            }
            it++;
        }
        ll curans=S.query(0LL,S.N-1,1,0,S.N-1).a;
        if(curans<=*it) {ans=min(ans,curans);}
        it++;
    }
    cout<<ans<<endl;
    return 0;
}

Compilation message (stderr)

FuelStation.cpp: In function 'void Out(std::vector<long long int>)':
FuelStation.cpp:14:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 | #define REP(i,a,b) for(ll i=a; i<b; i++)
......
   23 | void Out(vector<ll> x) {REP(i,0,x.size()) {cout<<x[i]<<" ";} cout<<endl;}
      |                             ~~~~~~~~~~~~
FuelStation.cpp:23:25: note: in expansion of macro 'REP'
   23 | void Out(vector<ll> x) {REP(i,0,x.size()) {cout<<x[i]<<" ";} cout<<endl;}
      |                         ^~~
FuelStation.cpp: In constructor 'ST::ST(std::vector<long long int>)':
FuelStation.cpp:14:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 | #define REP(i,a,b) for(ll i=a; i<b; i++)
......
   72 |         REP(i,0,arr.size()) {SV X(arr[i]); ar.pb(X);}
      |             ~~~~~~~~~~~~~~       
FuelStation.cpp:72:9: note: in expansion of macro 'REP'
   72 |         REP(i,0,arr.size()) {SV X(arr[i]); ar.pb(X);}
      |         ^~~
FuelStation.cpp: In function 'int main()':
FuelStation.cpp:14:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 | #define REP(i,a,b) for(ll i=a; i<b; i++)
......
  149 |             REP(i,0,m[*it].size())
      |                 ~~~~~~~~~~~~~~~~~
FuelStation.cpp:149:13: note: in expansion of macro 'REP'
  149 |             REP(i,0,m[*it].size())
      |             ^~~

• Subtask 1: 7 / 7
• Subtask 2: 13 / 13
• Subtask 3: 17 / 17
• Subtask 4: 12 / 12
• Subtask 5: 19 / 19
• Subtask 6: 11 / 11
• Subtask 7: 21 / 21