Submission #525285

#	Time	Username	Problem	Language	Result	Execution time	Memory
525285		sicho_mohit	Lasers (NOI19_lasers)	C++14	100 / 100	331 ms	41284 KiB

lasers

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define ff first
#define ss second
using namespace std ;
const int N=1e5+5;
int main ()
{
    ll n , k ;
    cin >> n >> k ;
    vector<vector<ll>>prefix(k+1);
    for (int i=0;i<k;i++)
    {
        int t ;
        cin >> t ;
        ll sum=0;
        prefix[i].pb(0);
        for (int j=0;j<t;j++)
        {
            ll  a;
            cin >> a ;
            sum+=a;
            prefix[i].pb(sum);
        }
    }
    vector<pair<ll,ll>>ans;
    // start from each row 
    for (int i=0;i<k;i++)
    {
        // work on this row 
        for (int j=1;j<prefix[i].size();j++)
        {
            ll l=prefix[i][j-1]+1;
            ll r=(n-(prefix[i][prefix[i].size()-1]-prefix[i][j]));
            ll s=r-l+1;
            ll w=prefix[i][j]-prefix[i][j-1];
            if(2*w-s>0)
            {
                ans.pb({r-w+1,l+w-1});
            }
        }
    }
    sort(ans.begin(),ans.end());
    if(ans.size()==0)
    cout<<"0"<<"\n";
    else
    {
        ll emax=ans[0].ss;
        ll finalans=ans[0].ss-ans[0].ff+1;
        for (int i=1;i<ans.size();)
        {
            while(ans[i].ss<=emax&&i<ans.size())
            {
                i++;
            }
            if(i<ans.size())
            {
            if(ans[i].ff>emax)
            {
                finalans+=ans[i].ss-ans[i].ff+1;
            }
            else if(ans[i].ff==emax)
            {
                finalans+=ans[i].ss-ans[i].ff;
            }
            else
            {
                finalans+=ans[i].ss-emax;
            }
            emax=max(emax,ans[i].ss);
            i++;
            }
        }
        cout<<finalans<<"\n";
    }
}

Compilation message (stderr)

lasers.cpp: In function 'int main()':
lasers.cpp:32:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |         for (int j=1;j<prefix[i].size();j++)
      |                      ~^~~~~~~~~~~~~~~~~
lasers.cpp:51:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |         for (int i=1;i<ans.size();)
      |                      ~^~~~~~~~~~~
lasers.cpp:53:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |             while(ans[i].ss<=emax&&i<ans.size())
      |                                    ~^~~~~~~~~~~
lasers.cpp:57:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |             if(i<ans.size())
      |                ~^~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 14 / 14
• Subtask 3: 20 / 20
• Subtask 4: 21 / 21
• Subtask 5: 22 / 22
• Subtask 6: 13 / 13