Submission #543789

#	Time	Username	Problem	Language	Result	Execution time	Memory
543789		robertbarbu27	Autobahn (COI21_autobahn)	C++14	0 / 100	1 ms	212 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;
    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 (stderr)

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);
      |                       ~~~~~~~^~~~~~~~

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