Mai intai trebuie sa te autentifici.
Cod sursa(job #355040)
Utilizator | Data | 10 octombrie 2009 07:08:09 | |
---|---|---|---|
Problema | Secventa | Scor | 80 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 1.22 kb |
#include <stdio.h>
#define MAXN 500000
#define FISIN "secventa.in"
#define FISOUT "secventa.out"
FILE *fin, *fout;
class strange_queue {
public:
struct elem {
elem(int k = 0, int v = 0) : key(k), value(v) { }
int key, value;
};
void add(const elem& e) {
while (stop > start && e.value < m_list[stop - 1].value) --stop;
m_list[stop] = e; ++stop;
}
void del(int key) {
if (m_list[start].key == key) ++start;
}
int min() { return m_list[start].value; }
private:
elem m_list[MAXN];
int start, stop;
};
strange_queue q;
int main() {
fin = fopen(FISIN, "rt");
fout = fopen(FISOUT, "wt");
int n, k; fscanf(fin, "%d %d", &n, &k);
for (int i = 0; i < k; ++i) {
int a;
fscanf(fin, "%d", &a);
q.add(strange_queue::elem(i, a));
}
int best_start = 0; int best_base = q.min();
for (int i = k; i < n; ++i) {
int a; fscanf(fin, "%d", &a);
int start = i - k;
q.del(start);
q.add(strange_queue::elem(i, a));
int m = q.min();
if (m > best_base) {
best_base = m;
best_start = i - k + 1;
}
}
best_start++;
fprintf(fout, "%d %d %d\n", best_start, best_start + k - 1, best_base);
fclose(fout);
fclose(fin);
return 0;
}