oj.uz

Submission #990944

# Submission time Handle Problem Language Result Execution time Memory
990944 2024-05-31T20:47:34 Z alexdd Autobahn (COI21_autobahn) C++17
0 / 100
 2 ms 4444 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;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 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 2 ms 4440 KB Output is correct
6 Correct 2 ms 4444 KB Output is correct
7 Correct 2 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Incorrect 1 ms 4444 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 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 2 ms 4440 KB Output is correct
6 Correct 2 ms 4444 KB Output is correct
7 Correct 2 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Incorrect 1 ms 4444 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 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 2 ms 4440 KB Output is correct
6 Correct 2 ms 4444 KB Output is correct
7 Correct 2 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Incorrect 1 ms 4444 KB Output isn't correct
11 Halted 0 ms 0 KB -