Pagini recente » Cod sursa (job #1520606) | Cod sursa (job #2110893) | Istoria paginii runda/aparare | Monitorul de evaluare | Cod sursa (job #1048554)
#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <limits>
#include <algorithm>
#include <time.h>
#include <stdlib.h>
using namespace std;
void read_first_number(char* buf, int& no, char** buf2)
{
int number = 0;
bool end_number = false;
bool number_started = false;
int k = -1;
while (!end_number)
{
k++;
char c = buf[k] - '0';
if (0 <= c && c <= 9)
{
number = 10 * number + c;
number_started = true;
}
else if (number_started) end_number = true;
}
no = number; *buf2 = buf + k;
}
void generate_sequence(int N, int K, int MAX_VAL, string file)
{
srand((unsigned int) time(0));
ofstream ofs(file);
ofs << N << " " << K << endl;
for (int i = 1; i <= N; i++) ofs << rand() % MAX_VAL << " ";
ofs.close();
}
//int pb_014_secventa()
int main()
{
string in_file = "secventa.in";
string out_file = "secventa.out";
const int MAX_N = 500000;
//generate_sequence(MAX_N, 100000, 30000, in_file);
//clock_t start_time = clock();
int N, K;
int x[MAX_N + 1];
ifstream ifs(in_file);
/*ifs.seekg(0, ios::end);
std::streamoff length = ifs.tellg();
ifs.seekg(0, ios::beg);
char* buffer = new char[length+1];
ifs.read(buffer, length);
char* buf2;
read_first_number(buffer, N, &buf2);
read_first_number(buf2, K, &buf2);
for (int i = 1; i <= N; i++) read_first_number(buf2, x[i], &buf2);*/
//delete[] buffer;
ifs >> N >> K;
for (int i = 1; i <= N; i++) ifs >> x[i];
ifs.close();
//read the array
//for (int i = 1; i <= N; i++) ifs >> x[i];
//clock_t end_time_read = clock();
//cout << (double)(end_time_read - start_time) / CLOCKS_PER_SEC << endl;
int deq[MAX_N + 1];
//deq[1] = x[1];
int Fd = 1, Ld = 0;
int id_mm = 1, max_min = numeric_limits<int>::min();
for (int i = 1; i <= N; i++)
{
//insert one element in the proper location in the deq
while (Ld - Fd >= 0 && x[i] < deq[Ld]) Ld--;
deq[++Ld] = x[i];
if (i >= K)
{
int cmin = deq[Fd];
if (cmin > max_min) { max_min = cmin; id_mm = i; }
if (x[i - K + 1] == deq[Fd]) Fd++; //pop the first element
}
}
ofstream ofs(out_file);
ofs << id_mm - K + 1 << " " << id_mm << " " << max_min;
ofs.close();
//clock_t end_time = clock();
//cout << (double) (end_time - start_time) / CLOCKS_PER_SEC << endl;
return 0;
}