Pagini recente » Cod sursa (job #866652) | Cod sursa (job #2256142) | Cod sursa (job #1439591) | Cod sursa (job #2931287) | Cod sursa (job #1777099)
#include <fstream>
#include <vector>
#include <algorithm>
#include <utility>
#include <memory>
#include <iterator>
#include <deque>
#include <tuple>
struct file_manip {
std::ifstream fin;
std::ofstream fout;
file_manip(const char* filename) {
std::string infilename = std::string(filename) + ".in";
std::string outfilename = std::string(filename) + ".out";
fin.open(infilename.c_str());
fout.open(outfilename.c_str());
}
template <class T>
file_manip& operator << (const T& rhs) {
fout << rhs;
return *this;
}
template <class T>
file_manip& operator >> (T& rhs) {
fin >> rhs;
return *this;
}
template <class T>
std::ostream_iterator<T> GetOstreamIterator() {
return std::ostream_iterator<T>(fout);
}
template <class T>
std::istream_iterator<T> GetIstreamIterator() {
return std::istream_iterator<T>(fin);
}
template <class T>
std::vector<T> ReadVector(int size)
{
std::vector<int> v;
v.reserve(size);
std::copy_n(GetIstreamIterator<int>(), size, std::back_inserter(v));
return v;
}
};
struct EntryPair
{
int pos, val;
EntryPair(int pos, int val) : pos(pos), val(val) {}
};
int main()
{
int N,K;
file_manip fm("secventa");
fm >> N >> K;
std::deque<EntryPair> dq;
auto sol = std::make_tuple(0, 0, -30001);
for (auto i = 1; i <= N; ++i)
{
int x;
fm >> x;
while (!dq.empty() && dq.back().val >= x)
dq.pop_back();
dq.emplace_back(i, x);
while (!dq.empty() && dq.front().pos <= i - K)
dq.pop_front();
if (i >= K && dq.front().val > std::get<2>(sol))
{
sol = std::make_tuple(i - K + 1, i, dq.front().val);
}
}
fm << std::get<0>(sol) << " " << std::get<1>(sol) << " " << std::get<2>(sol) << "\n";
}