Untitled
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 ; } } }