oj.uz

Submission #543857

# Submission time Handle Problem Language Result Execution time Memory
543857 2022-03-31T13:58:22 Z 1BeeNY1 Autobahn (COI21_autobahn) C++17
100 / 100
 169 ms 9424 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
long long n,k,x,nr,tr,pr,numbers;
long long ans=0;
long long suma[300005];
 
struct curse
{
    int st,dr;
    long long cost;
} v[300005];
 
struct evenimente
{
    int st,dr;
} ev[300005];
 
struct intervale
{
    int st,dr;
    long long cost;
} need[300005];
 
pair<int,int>conteaza[300005];
pair<int,int>pozitii[300005];
 
int main()
{
    cin>>n>>k>>x;
 
    for(int i=1; i<=n; i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
 
        if(a+b-1<c)
        {
            nr++;
            pozitii[nr]= {a+b,1};
            nr++;
            pozitii[nr]= {c+1,-1};
        }
        conteaza[i]= {a,1};
        conteaza[n+i]= {c+1,-1};
    }
 
    ///intervalele unde se aplica costul
    sort(conteaza+1,conteaza+2*n+1);
    int ct=0;
 
    for(int i=1; i<=2*n; i++)
    {
        int val=conteaza[i].first;
        ct+=conteaza[i].second;
 
        while(i+1<=2*n&&conteaza[i+1].first==val)
        {
            i++;
            ct+=conteaza[i].second;
        }
 
        if(i==2*n) break;
        if(ct>=k)
        {
            if(tr&&ev[tr].dr==val-1) ev[tr].dr=conteaza[i+1].first-1;
            else
            {
                tr++;
                ev[tr].st=val;
                ev[tr].dr=conteaza[i+1].first-1;
            }
        }
    }
 
    ///intervalele cu cost
    sort(pozitii+1,pozitii+nr+1);
    ct=0;
 
    for(int i=1; i<=nr; i++)
    {
        int val=pozitii[i].first;
        ct+=pozitii[i].second;
 
        while(i+1<=nr&&pozitii[i+1].first==val)
        {
            i++;
            ct+=pozitii[i].second;
        }
 
        if(i==nr) break;
 
        if(ct!=0)
        {
            pr++;
            v[pr].st=val;
            v[pr].dr=pozitii[i+1].first-1;
            v[pr].cost=ct;
        }
    }
 
    if(tr==0||pr==0)
    {
        cout<<'0'<<'\n';
        return 0;
    }
 
    ///creez intervalele disjuncte prin care sa pot cauta binar raspunsul
    int poz=0;
    for(int i=1; i<=pr; i++)
    {
        while(poz+1<=tr&&v[i].st>ev[poz].dr) poz++;
        if(ev[poz].dr<v[i].st) break;
 
        if(ev[poz].st<=v[i].st&&v[i].dr<=ev[poz].dr)
        {
            numbers++;
            need[numbers].st=v[i].st;
            need[numbers].dr=v[i].dr;
            need[numbers].cost=v[i].cost;
 
            continue;
        }
 
        if(ev[poz].st<v[i].st)
        {
            numbers++;
            need[numbers].st=v[i].st;
            need[numbers].dr=ev[poz].dr;
            need[numbers].cost=v[i].cost;
            poz++;
        }
 
        if(poz>tr) break;
 
        while( poz<=tr&&v[i].st<ev[poz].st&&ev[poz].dr<=v[i].dr )
        {
            numbers++;
            need[numbers].st=ev[poz].st;
            need[numbers].dr=ev[poz].dr;
            need[numbers].cost=v[i].cost;
            poz++;
        }
        
        if(poz>tr) break;
 
        if(ev[poz].st<=v[i].dr)
        {
            numbers++;
            need[numbers].st=ev[poz].st;
            need[numbers].dr=v[i].dr;
            need[numbers].cost=v[i].cost;
            continue;
        }
    }
 
    for(int i=1; i<=numbers; i++) suma[i]=suma[i-1]+1LL*(need[i].dr-need[i].st+1)*need[i].cost;
 
    ///plec de la stanga la dreapta
    for(int i=1; i<=numbers; i++)
    {
        int rasp=i-1,st=i,dr=numbers,mid;
 
        while(st<=dr)
        {
            mid=(st+dr)/2;
 
            if(need[mid].dr<=need[i].st+x-1) rasp=mid,st=mid+1;
            else dr=mid-1;
        }
 
        long long ss=0;
        if(rasp!=i-1) ss=suma[rasp]-suma[i-1];
        rasp++;
        if(rasp<=numbers&&need[rasp].st<=need[i].st+x-1) ss+=1LL*(need[i].st+x-need[rasp].st)*need[rasp].cost;
 
        ans=max(ans,ss);
    }
    ///plec de la dreapta la stanga
    for(int i=1; i<=numbers; i++)
    {
        int rasp=i+1,st=1,dr=i,mid;
 
        while(st<=dr)
        {
            mid=(st+dr)/2;
 
            if(need[mid].st>=need[i].dr-x+1) rasp=mid,dr=mid-1;
            else st=mid+1;
        }
 
        long long ss=0;
        if(rasp!=i+1) ss=suma[i]-suma[rasp-1];
 
        rasp--;
 
        if(rasp>=1&&need[rasp].dr>=need[i].dr-x+1) ss+=1LL*(need[rasp].dr-need[i].dr+x)*need[rasp].cost;
 
        ans=max(ans,ss);
    }
 
    cout<<ans;
 
    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 284 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 284 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 2 ms 332 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 2 ms 340 KB Output is correct
17 Correct 2 ms 340 KB Output is correct
18 Correct 1 ms 380 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 284 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 2 ms 332 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 2 ms 340 KB Output is correct
17 Correct 2 ms 340 KB Output is correct
18 Correct 1 ms 380 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 169 ms 9176 KB Output is correct
22 Correct 163 ms 9268 KB Output is correct
23 Correct 159 ms 9272 KB Output is correct
24 Correct 153 ms 9308 KB Output is correct
25 Correct 152 ms 9176 KB Output is correct
26 Correct 162 ms 9184 KB Output is correct
27 Correct 153 ms 9252 KB Output is correct
28 Correct 143 ms 9164 KB Output is correct
29 Correct 152 ms 9424 KB Output is correct