//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;
}
Compilation message
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;
| ~^~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
38 ms |
13340 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
