Submission #543813

#	Time	Username	Problem	Language	Result	Execution time	Memory
543813		robertbarbu27	Autobahn (COI21_autobahn)	C++14	100 / 100	188 ms	10976 KiB

autobahn

#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;
     segments.push_back({-1e9,0});
    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(v[i].x==6) cout<<overcharged<<" ";
            if(nrpeople>=K)
            {
                segments.push_back({v[i].x,overcharged});
            }
            else segments.push_back({v[i].x,0});
            //if(v[i].)
        }
    }
    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=1;i<segments.size()-2;i++)
    {
       // cout<<segments[i].first<<" "<<segments[i].second<<'\n';
        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;
    ///check the end
    for(int i=segments.size()-2;i>=1;i--)
    {
        int finish=segments[i+1].first-1,rasp;
        if(segments[i].first>=X)
        {
            int st=0,dr=i;
            while(st<=dr)
            {
                int mij=(st+dr)/2;
                if(finish-segments[mij].first+1>=X)
                {
                    rasp=mij;
                    st=mij+1;
                }
                else dr=mij-1;
            }
        }
        ll rez=get_sum(i)-get_sum(rasp);
        int cate=finish-segments[rasp+1].first+1;
        rez+=1LL*(X-cate)*1LL*segments[rasp].second;
        ans=max(ans,rez);
    }
    cout<<ans;
   // cout<<ans<<" ";






}

Compilation message (stderr)

autobahn.cpp: In function 'int main()':
autobahn.cpp:82: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]
   82 |     for(int i=0;i<segments.size()-1;i++)
      |                 ~^~~~~~~~~~~~~~~~~~
autobahn.cpp:88: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]
   88 |     for(int i=1;i<segments.size()-2;i++)
      |                 ~^~~~~~~~~~~~~~~~~~
autobahn.cpp:46:9: warning: unused variable 'nrclienti' [-Wunused-variable]
   46 |     int nrclienti=0;
      |         ^~~~~~~~~
autobahn.cpp:129:38: warning: 'rasp' may be used uninitialized in this function [-Wmaybe-uninitialized]
  129 |         int cate=finish-segments[rasp+1].first+1;
      |                                  ~~~~^~
autobahn.cpp:103:30: warning: 'rasp' may be used uninitialized in this function [-Wmaybe-uninitialized]
  103 |         long long rez=get_sum(rasp-1)-get_sum(i-1);
      |                       ~~~~~~~^~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 50 / 50