Pagini recente » Cod sursa (job #1374367) | Cod sursa (job #1817801) | Cod sursa (job #3333423) | Cod sursa (job #1903528) | Cod sursa (job #975665)
Cod sursa(job #975665)
#include <iostream>
#include <fstream>
using namespace std;
int k, n, v[500001], x[500001], xlen, xbase, xmin, xmax;
void print(){
cout << endl;
cout << n << " " << k << endl;
for(int i = 0; i < n; i ++){
cout << v[i] << " ";
}
cout << endl;
cout << xmin+1 << " " << xmax+1 << " " << v[xbase] << endl;
cout << endl;
}
void printx(){
int i;
for(i = 0; i < xlen; i ++){
cout << x[i] << " ";
}
cout << endl;
for(i = 0; i < xlen; i ++){
cout << v[x[i]] << " ";
}
cout << endl << endl;
}
void insertion(int p){
int i, j;
for(i = 0; i < xlen; i ++){
if(v[x[i]] > v[p]){
for(j = xlen - 1; j >= i; j --){
x[j+1] = x[j];
}
break;
}
}
x[i] = p;
xlen ++;
//printx();
}
void removemin(){
int min, i, ylen, y[500001];
min = x[0];
ylen = 0;
for(i = 0; i < xlen; i++){
if(x[i] > min){
y[ylen] = x[i];
ylen ++;
}
}
xlen = ylen;
for(i = 0; i < xlen; i ++){
x[i] = y[i];
}
//printx();
}
void read(){
ifstream fi("secventa.in");
fi >> n;
fi >> k;
for (int i = 0; i < n; i ++){
fi >> v[i];
}
fi.close();
}
void write(){
ofstream fo("secventa.out");
fo << xmin+1 << " " << xmax+1 << " " << v[xbase];
fo.close();
}
void compute(){
int i, j;
xlen = 0;
for(i = 0; i < k; i ++){
insertion(i);
}
xbase = x[0];
xmin = x[0];
xmax = x[0];
for(j = 0; j < xlen; j ++){
if(x[j] > xmax){
xmax = x[j];
}
if(x[j] < xmin){
xmin = x[j];
}
}
while(i < n){
removemin();
for(j = xlen; j < k; j ++){
insertion(i);
i ++;
}
if(v[x[0]] > v[xmin]){
xbase = x[0];
xmin = x[0];
xmax = x[0];
for(j = 0; j < xlen; j ++){
if(x[j] > xmax){
xmax = x[j];
}
if(x[j] < xmin){
xmin = x[j];
}
}
}
}
//print();
}
int main(void){
read();
compute();
write();
return 0;
}