Submission #949906

#	Time	Username	Problem	Language	Result	Execution time	Memory
949906		sondos225	Fuel Station (NOI20_fuelstation)	C++17	100 / 100	460 ms	53708 KiB

FuelStation

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T>using ordered_set = tree<T,null_type,less_equal<T>,rb_tree_tag,tree_order_statistics_node_update>;//find_by_order(ind);
//order_of_key()
#define int long long
#define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
#define pb push_back
#define yes "YES"
#define no "NO"
#define bigg INT_MAX
#define debug(x) cout<<(#x)<<" = " <<x<<endl;
#define all(x) x.begin(),x.end()
#define sz size()
#define nn '\n'
#define mms(x,y) memset(x,y,sizeof(x))
#define forr(i,j,n) for (int i=j; i<n; i++)
#define forn(i,j,n) for (int i=j; i>n; i--)
#define fi first
#define se second
#define la "LA"
#define cinn(x,y) for(int i=0; i<y; i++) cin>>x[i];
#define pii pair<int,int>
//
//int fact(int x)
//{
//    int w=1;
//    forr(i,1,x+1) w*=i;
//////}
//bool cmp(pair<int,pii> a, pair<int,pii> b)
//{
//    if (get<0>(a)==get<0>(b) && get<1>(a)==get<1>(b)) return get<2>(a)<get<2>(b);
//    if (get<0>(a)==get<0>(b)) return get<1>(a)<get<1>(b);
//    return get<0>(a)<get<0>(b);
//}
signed main()
{
//    #ifndef LOCAL
//    freopen("lifeguards.in","r",stdin);
//    freopen("lifeguards.out","w", stdout);
//    #endif
    fast
    int n,d;
    cin>>n >>d;
//    int p[n],a[n],b[n];
vector<pair<int,pii>> t(n+1);
    forr(i,0,n)
    {
        cin>>t[i].fi >>t[i].se.fi >>t[i].se.se;
    }
    //cout<<la<<la<<la<<la<<d<<endl;
    t[n].fi=d;
    t[n].se.fi=0;
    t[n].se.se=0;
//    get<0>(t[n-1])=d;
//    get<1>(t[n-1])=0;
//    get<2>(t[n-1])=0;
    sort(all(t));
  //  int s=, e=d;
  int f=t[0].fi;
  ordered_set <int> s;
  map<int,int> m;
  int idx=0;
  int left=f;
    forr(i,0,n+1)
    {
        int x=t[i].fi, a=t[i].se.fi, b=t[i].se.se;
        //+a lw <=b at x
       // cout<<yes<<x<<' '<<a<<' '<<b<<endl;
        //cout<<no<<x<<' '<<idx<<' '<<left<<endl;
        if (idx+left<x)
        {
            //invalid lazm nzawed
            int need=x-(idx+left);
            f+=need;
           // cout<<la<<' '<<need<<endl;
            for(auto y:s)
            {
                if (y<f)
                {
                   // cout<<y<<' '<<f<<endl;
                    f+=m[y];
                    m[y]=0;
                }
                else break;
            }
            left+=need;
        }
        if (idx+left>=x)
        {
            int done=(x-idx);
            idx+=done;
            left-=done;
            if (f<=b)
            {
                left+=a;
                s.insert(b);
                m[b]+=a;
            }
        }

      //  if (x==d) break;
    }
    cout<<f;
    return 0;
}

• 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