Cod sursa(job #2750583)

Utilizator hungntnktpHungntnktp hungntnktp Data 12 mai 2021 05:50:42
Problema Secventa Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.53 kb
#include <bits/stdc++.h>
using namespace std;
#define in ({int x=0;int c=getchar(),n=0;for(;!isdigit(c);c=getchar()) n=(c=='-');for(;isdigit(c);c=getchar()) x=x*10+c-'0';n?-x:x;})
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l,int r){return l+rng()%(r-l+1);}
#define fasty ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define fori(x,a,b) for(int x=a;x<=b;x++)
#define ford(x,a,b) for(int x=a;x>=b;x--)
#define forv(a,b) for(auto&a:b)
#define fi first
#define se second
#define pb push_back
#define ii pair<int,int>
#define mt make_tuple
#define all(a) a.begin(),a.end()
#define reset(f,x) memset(f,x,sizeof(f))
#define getbit(x,i) ((x>>i)&1)
#define batbit(x,i) (x|(1ll<<i))
#define tatbit(x,i) (x&~(1<<i))
#define gg exit(0);

const int maxn = 5e5 + 10;
int n,k,a[maxn];
main()
{
   //freopen("task.inp","r",stdin);
   fasty;
   freopen("secventa.in","r",stdin);
   freopen("secventa.out","w",stdout);
   cin>>n>>k;
   fori(i,1,n) cin>>a[i];

   deque<int> dq;
   int kq = -1e9,pos = 0;
   fori(i,1,n)
   {
       while(!dq.empty() && a[dq.back()]>=a[i]) dq.pop_back();
       dq.push_back(i);
       if(dq.front()<i-k+1) dq.pop_front();
       if(i>=k)
       {
           if(kq < a[dq.front()])
           {
               kq = a[dq.front()];
               pos = i;
           }
       }
   }

   int st = pos-k+1;
   if(pos-k>=1)
   {
       ford(i,pos-k,1)
       {
           if(a[i]<kq) {st=i+1;break;}
       }
   }
   cout<<st<<" "<<pos<<" "<<kq;
}