一个奇怪的问题

P1886 滑动窗口 /【模板】单调队列

dsl2002 @ 2017-01-25 18:32:10

一道一样的题,一份一样的代码,放在洛谷和另一个oj上AC,但在POJ上怎么会TLE啊??

  • 附上丑丑的代码

···cpp

#include <cstdio>
#include <cstdlib>
#include <deque>
using namespace std;
const int maxn = (int)1e6 + 5;
struct point {
    int a, t;    
};
deque<point> dmin, dmax;
int a[maxn], Min[maxn], Max[maxn];
int n, k;
int main()
{
    freopen("input.in", "r", stdin);
    freopen("output.out", "w", stdout);
    int i;
    scanf("%d%d", &n, &k);
    for(i = 1; i <= n; i++)
      scanf("%d", &a[i]);
    for(i = 1; i <= n; i++) {
      while(!dmax.empty() && dmax.back().a <= a[i]) 
        dmax.pop_back();
      dmax.push_back((point){a[i], i});
      while(!dmin.empty() && dmin.back().a >= a[i]) 
        dmin.pop_back();
      dmin.push_back((point){a[i], i});
      if(i >= k) {
          Min[i - k + 1] = dmin.front().a; Max[i - k + 1] = dmax.front().a;
          if(dmin.front().t <= i - k + 1) dmin.pop_front(); 
        if(dmax.front().t <= i - k + 1) dmax.pop_front();
      }
    }
    for(i = 1; i <= n - k + 1; i++)
      printf("%d ", Min[i]);
    printf("\n");
    for(i = 1; i <= n - k + 1; i++)
      printf("%d ", Max[i]);
    return 0;
}
···

by afsg @ 2017-01-25 20:20:37

只能说明poj数据神


by litble @ 2017-06-20 15:01:05

在poj上G++会T改成C++就好了.....


|