# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
990945 |
2024-05-31T20:48:03 Z |
alexdd |
Autobahn (COI21_autobahn) |
C++17 |
|
1000 ms |
346196 KB |
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,k,lun,cate;
vector<pair<int,int>> v,v2;
map<int,int> mp,nrm;
int inv[400005];
int mars[400005],mars2[400005];
signed main()
{
ios_base::sync_with_stdio(0);cin.tie(0);
cin>>n>>k>>lun;
int le,ri,t;
for(int i=1;i<=n;i++)
{
cin>>le>>t>>ri;
for(int j=le;j<=ri;j++)mp[j]++;
v2.push_back({le,ri});
mp[le]++;
mp[ri]++;
mp[ri+1]++;
le+=t;
if(ri>=le)
{
v.push_back({le,ri});
mp[le]++;
}
}
for(auto it:mp)
{
nrm[it.first]=++cate;
inv[cate]=it.first;
}
for(auto x:v)
{
mars[nrm[x.first]]++;
mars[nrm[x.second+1]]--;
}
for(auto x:v2)
{
mars2[nrm[x.first]]++;
mars2[nrm[x.second+1]]--;
}
for(int i=1;i<=cate;i++)
{
mars2[i]+=mars2[i-1];
mars[i]+=mars[i-1];
//cout<<i<<" "<<mars2[i]<<" "<<mars[i]<<" mars\n";
//cout<<i<<" "<<inv[i]<<" inv\n";
}
for(int i=1;i<=cate;i++)
if(mars2[i]<k)
mars[i]=0;
int poz=1,sum=0,mxm=0;
for(int i=1;i<=cate;i++)
{
sum += mars[i]*(inv[i+1]-inv[i]);
while(inv[i]-inv[poz+1]+1 > lun)
{
sum -= mars[poz]*(inv[poz+1]-inv[poz]);
poz++;
}
mxm = max(mxm, sum - mars[poz]*((inv[i]-inv[poz]+1)-lun));
}
cout<<mxm;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4444 KB |
Output is correct |
2 |
Correct |
1 ms |
4444 KB |
Output is correct |
3 |
Correct |
1 ms |
4444 KB |
Output is correct |
4 |
Correct |
1 ms |
4444 KB |
Output is correct |
5 |
Correct |
1 ms |
4696 KB |
Output is correct |
6 |
Correct |
1 ms |
4444 KB |
Output is correct |
7 |
Correct |
1 ms |
4440 KB |
Output is correct |
8 |
Correct |
1 ms |
4444 KB |
Output is correct |
9 |
Correct |
1 ms |
4444 KB |
Output is correct |
10 |
Correct |
1 ms |
4444 KB |
Output is correct |
11 |
Correct |
1 ms |
4444 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4444 KB |
Output is correct |
2 |
Correct |
1 ms |
4444 KB |
Output is correct |
3 |
Correct |
1 ms |
4444 KB |
Output is correct |
4 |
Correct |
1 ms |
4444 KB |
Output is correct |
5 |
Correct |
1 ms |
4696 KB |
Output is correct |
6 |
Correct |
1 ms |
4444 KB |
Output is correct |
7 |
Correct |
1 ms |
4440 KB |
Output is correct |
8 |
Correct |
1 ms |
4444 KB |
Output is correct |
9 |
Correct |
1 ms |
4444 KB |
Output is correct |
10 |
Correct |
1 ms |
4444 KB |
Output is correct |
11 |
Correct |
1 ms |
4444 KB |
Output is correct |
12 |
Correct |
5 ms |
4700 KB |
Output is correct |
13 |
Correct |
5 ms |
4700 KB |
Output is correct |
14 |
Correct |
5 ms |
4700 KB |
Output is correct |
15 |
Correct |
5 ms |
4700 KB |
Output is correct |
16 |
Correct |
4 ms |
4700 KB |
Output is correct |
17 |
Correct |
5 ms |
4640 KB |
Output is correct |
18 |
Correct |
5 ms |
4700 KB |
Output is correct |
19 |
Correct |
4 ms |
4700 KB |
Output is correct |
20 |
Correct |
5 ms |
4700 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4444 KB |
Output is correct |
2 |
Correct |
1 ms |
4444 KB |
Output is correct |
3 |
Correct |
1 ms |
4444 KB |
Output is correct |
4 |
Correct |
1 ms |
4444 KB |
Output is correct |
5 |
Correct |
1 ms |
4696 KB |
Output is correct |
6 |
Correct |
1 ms |
4444 KB |
Output is correct |
7 |
Correct |
1 ms |
4440 KB |
Output is correct |
8 |
Correct |
1 ms |
4444 KB |
Output is correct |
9 |
Correct |
1 ms |
4444 KB |
Output is correct |
10 |
Correct |
1 ms |
4444 KB |
Output is correct |
11 |
Correct |
1 ms |
4444 KB |
Output is correct |
12 |
Correct |
5 ms |
4700 KB |
Output is correct |
13 |
Correct |
5 ms |
4700 KB |
Output is correct |
14 |
Correct |
5 ms |
4700 KB |
Output is correct |
15 |
Correct |
5 ms |
4700 KB |
Output is correct |
16 |
Correct |
4 ms |
4700 KB |
Output is correct |
17 |
Correct |
5 ms |
4640 KB |
Output is correct |
18 |
Correct |
5 ms |
4700 KB |
Output is correct |
19 |
Correct |
4 ms |
4700 KB |
Output is correct |
20 |
Correct |
5 ms |
4700 KB |
Output is correct |
21 |
Execution timed out |
1077 ms |
346196 KB |
Time limit exceeded |
22 |
Halted |
0 ms |
0 KB |
- |