#include <bits/stdc++.h>
#define pb push_back
#define ll long long
using namespace std;
ifstream f("teroristi2.in");
ofstream g("teroristi2.out");
int N,K,X;
struct event
{
int x;
int tip;
};
event v[400005];
int cnt=0;
bool cmp(event a,event b)
{
if(a.x==b.x)
{
return a.tip<b.tip;
}
return a.x<b.x;
}
long long sp[400005];
long long get_sum(int x)
{
if(x==-1) return 0;
return sp[x];
}
int main ()
{
cin>>N>>K>>X;
for(int i=1;i<=N;i++)
{
int l,t,r;
cin>>l>>t>>r;
v[++cnt]={l,2};
v[++cnt]={r+1,-2};
if(l+t<=r)
{
v[++cnt]={l+t,1};
v[++cnt]={r+1,-1};
}
}
sort(v+1,v+cnt+1,cmp);
int nrclienti=0;
int nrpeople=0,overcharged=0;
vector<pair<int,int> > segments;
for(int i=1;i<=cnt;i++)
{
if(v[i].tip==2)
{
nrpeople++;
}
if(v[i].tip==-2)
{
nrpeople--;
}
if(v[i].tip==1)
{
overcharged++;
}
if(v[i].tip==-1)
{
overcharged--;
}
if(v[i].x!=v[i-1].x)
{
if(nrpeople>=K)
{
segments.push_back({v[i].x,overcharged});
}
else segments.push_back({v[i].x,0});
}
}
segments.push_back({2e9,0});
long long ans=0;
for(int i=0;i<segments.size()-1;i++)
{
long long x=1LL*(segments[i+1].first-segments[i].first)*1LL*segments[i].second;
if(i==0) sp[i]=x;
else sp[i]=sp[i-1]+x;
}
for(int i=0;i<segments.size()-1;i++)
{
int st=i,dr=segments.size()-1,rasp;
while(st<=dr)
{
int mij=(st+dr)/2;
if(segments[mij].first-segments[i].first>=X)
{
rasp=mij;
dr=mij-1;
}
else st=mij+1;
}
rasp--;
long long rez=get_sum(rasp-1)-get_sum(i-1);
int cate=segments[rasp].first-segments[i].first;///how many we already have
rez=rez+1LL*(X-cate)*1LL*segments[rasp].second;
ans=max(ans,rez);
}
cout<<ans;
}
Compilation message
autobahn.cpp: In function 'int main()':
autobahn.cpp:79:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
79 | for(int i=0;i<segments.size()-1;i++)
| ~^~~~~~~~~~~~~~~~~~
autobahn.cpp:85:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
85 | for(int i=0;i<segments.size()-1;i++)
| ~^~~~~~~~~~~~~~~~~~
autobahn.cpp:46:9: warning: unused variable 'nrclienti' [-Wunused-variable]
46 | int nrclienti=0;
| ^~~~~~~~~
autobahn.cpp:99:30: warning: 'rasp' may be used uninitialized in this function [-Wmaybe-uninitialized]
99 | long long rez=get_sum(rasp-1)-get_sum(i-1);
| ~~~~~~~^~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
