제출 #1040148

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1040148		modwwe	Fuel Station (NOI20_fuelstation)	C++17	49 / 100	261 ms	15344 KiB

FuelStation

//https://www.instagram.com/_modwwe/
#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2")
#include<bits/stdc++.h>
#define int long long
//#define ll long long
#define down cout<<'\n';
#define debug cout<<" cucuucucuuu",down
#define NHP     ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
#define modwwe  int t;cin>>t; while(t--)
#define bit(i,j) (i>>j&1)
#define sobit(a) __builtin_popcountll(a)
#define task "test"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".ans","w",stdout)
#define pb push_back
#define checktime   cerr << (double)clock() / CLOCKS_PER_SEC * 1000  << " ms";
using namespace std;
void phongbeo();
const int inf=-1e18;
const int mod2=998244353;
const int  mod1=998244353;
struct icd
{
    long double a;
    int b;
};
struct ib
{
    int a;
    int b;
};
struct ic
{
    int a,b,c;
};
struct id
{
    int a,b,c,d;
};
struct ie
{
    int a,b,c,d,e;

};

int n,m,s1,s2,s4,s3,sf,k,s5,s6,mx,s7,s8,s9,mx2,res,dem2=0,dem=0,s33,dem3,l,r,mid;
int  i,s10,s12;
int kk;
int el=29;
main()
{
#ifndef ONLINE_JUDGE
    //fin(task),fou(task);
#endif
    NHP
    /// cin>>s1;
    //  modwwe
    phongbeo();
}
ic a[300002];
bool cmp(ic a,ic b)
{
    return a.a<b.a;
}
vector<int> v;
struct IT
{
    int t[1200001];
    int lazy[1200001];
    void ff(int x)
    {
        for(int i=x*2; i<=x*2+1; i++){
                if(t[i]<0) continue;
            t[i]+=lazy[x],
                  lazy[i]+=lazy[x];}
        lazy[x]=0;
    }
    void build(int node,int l,int r)
    {
        if(l==r)
        {
            t[node]=v[l-1];
            return;
        }
        int mid=l+r>>1;
        build(node<<1,l,mid);
        build(node<<1|1,mid+1,r);
        t[node]=max(t[node<<1],t[node<<1|1]);
    }

    void upd(int node,int l,int r,int l1,int r1,int x)
    {
    if(t[node]<0) return;
        if(l>r1||r<l1) return;
        if(l>=l1&&r<=r1)
        {
             if(x==inf) {t[node]=inf; lazy[node]=inf;
             }
             if(t[node]>=0){
             t[node]+=x;
             lazy[node]+=x;}
            return;
        }
        int mid=l+r>>1;
        ff(node);
        upd(node<<1,l,mid,l1,r1,x);
       upd(node<<1|1,mid+1,r,l1,r1,x);
        t[node]=max(t[node<<1],t[node<<1|1]);
    }
    int get(int node,int l,int r,int l1,int r1)
    { if(t[node]<0) return inf;
        if(l>r1||r<l1) return inf;
        if(l>=l1&&r<=r1) return t[node];
        ff(node);
        int mid=l+r>>1;
        return max(get(node<<1,l,mid,l1,r1),get(node<<1|1,mid+1,r,l1,r1));
    }
    void setup(int node,int l,int r)
    {
        if(l==r)
        {
            if(l==1)s2=1,s3=v[l-1];
            else s2=v[l-2],s3=v[l-1];
            return;
        }
    }
} st;
bool check(int x)
{int x2=x;
    for(int i=0; i<=n; i++)
    {
        if(x2<=v[a[i].c-1]) x+=a[i].b;
        x=x+a[i].a-a[i+1].a;
        if(x<0) return 0;
    }
    return 1;
}
void phongbeo()
{
    cin>>n>>m;
    for(int i=1; i<=n; i++)
        cin>>a[i].a>>a[i].b>>a[i].c,v.pb({a[i].c});
    sort(v.begin(),v.end());
        v.erase(unique(v.begin(), v.end()), v.end());
    for(int i=1; i<=n; i++) a[i].c=lower_bound(v.begin(),v.end(),a[i].c)-v.begin()+1;
    sort(a+1,a+1+n,cmp);
    a[n+1].a=m;
    s4=1;
    st.build(1,1,v.size());
   for(int i=0;i<=n; i++)
    {
        if(a[i].c!=0)
            st.upd(1,1,v.size(),1,a[i].c,a[i].b);
        st.upd(1,1,v.size(),1,v.size(),a[i].a-a[i+1].a);
        l=1;
        r=n;
        while(l<=r)
        {
            int mid=l+r>>1;
            if(st.get(1,1,v.size(),1,mid)<0)l=mid+1;
            else r=mid-1;
        }
      if(l-1!=0) st.upd(1,1,v.size(),1,l-1,inf);
     s4=max(s4,l);
    }
    if(s4==v.size()+1) {cout<<m; exit(0);}
 if(s4==1) l=1,r=v[s4-1];
 else l=v[s4-2]+1,r=v[s4-1];
 r=min(r,m-1);
 ///cout<<l<<" "<<r<<"\n";
  while(l<=r)
  {
      int mid=l+r>>1;
       if(check(mid))r=mid-1;
   else l=mid+1;
  }
  cout<<r+1;

}

컴파일 시 표준 에러 (stderr) 메시지

FuelStation.cpp:51:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   51 | main()
      | ^~~~
FuelStation.cpp: In member function 'void IT::build(long long int, long long int, long long int)':
FuelStation.cpp:86:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   86 |         int mid=l+r>>1;
      |                 ~^~
FuelStation.cpp: In member function 'void IT::upd(long long int, long long int, long long int, long long int, long long int, long long int)':
FuelStation.cpp:105:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  105 |         int mid=l+r>>1;
      |                 ~^~
FuelStation.cpp: In member function 'long long int IT::get(long long int, long long int, long long int, long long int, long long int)':
FuelStation.cpp:116:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  116 |         int mid=l+r>>1;
      |                 ~^~
FuelStation.cpp: In function 'void phongbeo()':
FuelStation.cpp:160:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  160 |             int mid=l+r>>1;
      |                     ~^~
FuelStation.cpp:167:10: 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]
  167 |     if(s4==v.size()+1) {cout<<m; exit(0);}
      |        ~~^~~~~~~~~~~~
FuelStation.cpp:174:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  174 |       int mid=l+r>>1;
      |               ~^~

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