1126
#include <vector> #include <list> #include <map> #include <set> #include <deque> #include <stack> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <cstdlib> #include <ctime> #include <math.h> #include <limits.h> #pragma comment(linker, "/STACK:16777216") using namespace std; // Datatypes typedef vector<int> vi; typedef vector<string> vs; typedef vector<vi> vvi; typedef pair<int,int> ii; typedef long long ll; typedef long double ld; // Define #define sz(a) int((a).size()) #define pb push_back #define all(c) (c).begin(),(c).end() #define present(c,x) ((c).find(x) != (c).end()) #define cpresent(c,x) (find(all(c),x) != (c).end()) #define FOR(_i,_n) for(int (_i) = 0; (_i) < (_n); (_i)++) #define mp make_pair // Constants const double eps = 1e-8; const double PI = 3.1415926535897932384626433832795; #define INPUT_FILE "input.txt" #define OUTPUT_FILE "output.txt" inline int nlz(unsigned x) { int n; if (x == 0) return(32); n = 0; if (x <= 0x0000FFFF) {n = n +16; x = x <<16;} if (x <= 0x00FFFFFF) {n = n + 8; x = x << 8;} if (x <= 0x0FFFFFFF) {n = n + 4; x = x << 4;} if (x <= 0x3FFFFFFF) {n = n + 2; x = x << 2;} if (x <= 0x7FFFFFFF) {n = n + 1;} return n; } /* for RMQ */ vector< vi > M; void init_rmq(vi &A) { int k = 31 - nlz(sz(A)); M.resize(k+1); FOR(i,k+1) { M[i].resize(sz(A)); } } void rmq_prep(vi &A) { int i, j; for (i = 0; i < sz(A); i++) M[0][i] = i; for (j = 1; 1 << j <= sz(A); j++) { for (i = 0; i + (1 << j) - 1 < sz(A); i++) { if (A[M[j - 1][i]] < A[M[j - 1][i + (1 << (j - 1))]]) M[j][i] = M[j - 1][i]; else M[j][i] = M[j - 1][i + (1 << (j - 1))]; } } } int rmq(vi &A, int i, int j) { int k = 31 - nlz(j-i+1); if(A[ M[k][i] ] <= A[ M[k][j - (1<<k) + 1] ]) return M[k][i]; else return M[k][j - (1<<k) + 1]; } int main(void) { #ifdef ALEX freopen("input.in", "r", stdin); freopen("output.out", "w", stdout); #else //freopen(INPUT_FILE, "r", stdin); //freopen(OUTPUT_FILE, "w", stdout); #endif int t; int m; vi L; cin >> m; cin >> t; while(t != -1) { L.pb(t); cin >> t; } init_rmq(L); rmq_prep(L); FOR(i,sz(L) - m+1) { cout << L[rmq(L, i, i + m-1)] << endl; } return 0; }
page revision: 0, last edited: 12 May 2007 21:45