Untitled

mail@pastecode.io avatar
unknown
plain_text
3 years ago
2.2 kB
3
Indexable
Never
#include<bits/stdc++.h>
#define fr(i,j,n)   for(int i=j;i<n;i++)
#define pb          push_back
#define rf(i,j,p)   for(int i=p-1;i>=j;i--)
#define vi          vector<int>
#define vll         vector<long long>
#define ll          long long
#define hmm         "\n"
#define sp          " "
#define srt(v)      sort(v.begin(), v.end());
#define ww           int tc ; cin >> tc ; while(tc--)
#define down        cout<<hmm;
#define faaast      ios_base::sync_with_stdio(0);cin.tie(nullptr);
#include <iostream>
#include <fstream>
using namespace std;


ll arr[1000006];
ll longestSubArrLens[1000006];
ll minSubArrLens[1000006];


int bsearch(int l , int r , ll cap)
{

    //returns longest possible subarray length from index l. l inclusive.
    int m ;
    int lo = l  , hi = r ;
    while(lo<hi)
    {
        m = (lo+hi)/2;
        if(arr[m]>=cap){
            hi = m ;
        }
        else if(arr[m]<cap){
            lo = m+1;
        }
    }

    if(lo < r && arr[lo] < cap) {
       lo++;
    }
    //cout<<l<<"-------"<<lo-l<<hmm;
    longestSubArrLens[l]=lo-l;

    return lo-l ;
}


int main()
{
   memset(arr,0, sizeof arr);
   ll n,f, mx = 0, idx = 0 ; cin >> n ;  string s ; cin >> s ;

   if(s[s.size()-1]=='M')f=1;
   else if(s[s.size()-1]=='G')f=1024;
   else if(s[s.size()-1]=='T')f=1024*1024;

   s.pop_back();
   ll cap = (ll)stoi(s);
   cap*=f;

   fr(i,1,n+1)cin>>arr[i];
   fr(i,1,n+1)arr[i]+=arr[i-1];

   if(n==1){
        cout<<1<<sp<<-1<<hmm;
        return 0;
   }

    fr(i,1,n+1){
       bsearch(i,n+1,cap+arr[i-1]);
    }

    ll minLen = n;
    fr(i,1,n+1)
    {
        minLen = min(minLen , longestSubArrLens[i]);
        minSubArrLens[i] = minLen ; //min subarray len upto index i
    }

  //fr(i,1,n+1)cout<<minSubArrLens[i]<<sp; down ;

    int R = n ;

    fr(i,1,n+1)
    {
        if(minSubArrLens[i]==(n-i+1)){
            R = minSubArrLens[i];
            cout<<R<<sp;
            break ;
        }
    }

    if( R == 1 ){
        cout<<-1<<hmm;
        return 0;
    }

    fr(i,1,n+1)
    {
        if(minSubArrLens[i]==R){
            cout<<i<<hmm;
            break ;
        }
    }


}