제출 #1040044

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1040044		modwwe	Fuel Station (NOI20_fuelstation)	C++17	0 / 100	38 ms	13340 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=-2e9;
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[200001];
bool cmp(ic a,ic b)
{
    return a.a<b.a;
}
vector<int> v;
struct IT
{
    int t[800001];
    int lazy[800001];
    void ff(int x)
    {
        for(int i=x*2; i<=x*2+1; i++)
            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(l>=l1&&r<=r1)
        {
            t[node]+=x;
            lazy[node]+=x;
            return;
        }
        int mid=l+r>>1;
        ff(node);
        upd(node<<1,l,mid,l1,r1,x);
        if(mid+1<=r1)  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(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,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;
        }
        setup(node<<1,l,mid);
        if(s2==-1&&s3==-1)
         setup(node<<1|1,mid+1,r);
    }
} 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;
    for(int i=0; i<=n; i++)
    {
        if(a[i].c!=0)
            st.upd(1,1,v.size(),1,a[i].c,a[i].a);
        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!=0)
            st.upd(1,1,v.size(),1,l-1,inf);
    }
    s2=-1;
    s3=-1;
    st.setup(1,1,v.size());
     if(s2==-1) {cout<<m; exit(0);}
    l=s2;
    r=s3;
    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:85:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   85 |         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:99:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   99 |         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:110:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  110 |         int mid=l+r>>1;
      |                 ~^~
FuelStation.cpp: In function 'void phongbeo()':
FuelStation.cpp:155:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  155 |             int mid=l+r>>1;
      |                     ~^~
FuelStation.cpp:170:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  170 |         int mid=l+r>>1;
      |                 ~^~

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