Pagini recente » Cod sursa (job #1491563) | Cod sursa (job #2315793) | Cod sursa (job #3144669) | Cod sursa (job #1969256) | Cod sursa (job #2327827)
/*
____ _____ ____ _____ _____ ____ _____ ____ _ _ ___ _____
| _ \ | ____| / ___| | ____| |_ _| | _ \ | ____| | __ ) | | | | |_ _| | ____|
| | | | | _| | | | _| | | | |_) | | _| | _ \ | | | | | | | _|
| |_| | | |___ | |___ | |___ | | | _ < | |___ | |_) | | |_| | | | | |___
|____/ |_____| \____| |_____| |_| |_| \_\ |_____| |____/ \___/ |___| |_____|
____ _ ____ ____ _____ ____ ___
| _ \ / \ | _ \ / ___| | ____| | _ \ |__ \
| |_) | / _ \ | |_) | \___ \ | _| | |_) | / /
| __/ / ___ \ | _ < ___) | | |___ | _ < |_|
|_| /_/ \_\ |_| \_\ |____/ |_____| |_| \_\ (_)
_ _ _ _ __ __ ___ ___ _ __ __
| \ | | | | | | \ \ / / / _ \ |_ _| / \ | \/ |
| \| | | | | | \ \ / / | | | | | | / _ \ | |\/| |
| |\ | | |_| | \ V / | |_| | | | / ___ \ | | | |
|_| \_| \___/ \_/ \___/ |___| /_/ \_\ |_| |_|
____ _ _____ _ _ ____
/ ___| / \ | ___| | | | | | _ \
\___ \ / _ \ | |_ | | | | | |_) |
___) | / ___ \ | _| | |_| | | _ < _ _ _
|____/ /_/ \_\ |_| \___/ |_| \_\ (_) (_) (_)
_ _ ___ ___ _ __ __
__| | __ _ / | / _ \ / _ \ (_)/ / _ \ \
/ _` | / _` | | | | | | | | | | | / / (_) | |
| (_| | | (_| | | | | |_| | | |_| | / /_ _ | |
\__,_| \__,_| |_| \___/ \___/ /_/(_) (_) | |
/_/
*/
//#include <iostream>
#include <queue>
#include <stack>
#include <map>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <set>
#include <algorithm>
#include <bitset>
#include <time.h>
#include <tuple>
#include <fstream>
#include <iomanip>
#include <utility>
#pragma warning "da 100% din tine. :)"
#define nl '\n'
#define cnl cout << '\n';
#define pb(x) push_back(x)
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define ll long long
#define ull unsigned ll
#ifdef INFOARENA
#define ProblemName "secventa"
#endif
#define MCONCAT(A, B) A B
#ifdef ProblemName
#define InFile MCONCAT(ProblemName, ".in")
#define OuFile MCONCAT(ProblemName, ".out")
#else
#define InFile "a.in"
#define OuFile "a.out"
#endif
//start copied part
class InParser {
private:
FILE *fin;
char *buff;
int sp;
char read_ch() {
sp++;
if (sp == 4096) {
sp = 0;
fread(buff, 1, 4096, fin);
}
return buff[sp];
}
public:
InParser(const char *nume) {
fin = fopen(nume, "r");
buff = new char[4096]();
sp = 4095;
}
InParser &operator>>(int &n) {
char c;
while (!isdigit(c = read_ch()) && c != '-');
int sgn = 1;
if (c == '-') {
n = 0;
sgn = -1;
} else
n = c - '0';
while (isdigit(c = read_ch()))
n = 10 * n + c - '0';
n *= sgn;
return *this;
}
};
//end copied part
using namespace std;
InParser cin(InFile);
ofstream cout(OuFile);
template<class v, class type>
void print(v Vector, type nr) {
for_each(all(Vector), [](type x) {
cout << x << ' ';
});
}
void nimic() {
return;
}
deque<int> dq;
int arr[500001];
ll sum = 0;
int el;
int main() {
freopen(InFile, "r", stdin);
freopen(OuFile, "w", stdin);
ios_base::sync_with_stdio(false);
clock_t tStart = clock();
int k, n, globalmin = -9999999;
cin >> n >> k;
int x = -1;
for (int i = 1; i <= n; ++i) {
cin >> arr[i];
}
for (int i = 1; i <= n; ++i) {
while (!dq.empty() && arr[dq.back()] >= arr[i])
dq.pop_back();
dq.push_back(i);
if (i - k == dq.front())
dq.pop_front();
if (i >= k && arr[dq.front()] > globalmin) {
globalmin = arr[dq.front()];
x = i;
}
}
cout << x - k + 1 << ' ' << x << ' ';
cout << globalmin;
printf("\nTime taken: %.2fs\n", (double) (clock() - tStart) / CLOCKS_PER_SEC);
}