Fraction @ 2018-08-24 16:06:16
RT,线段树是要开4倍空间,然鹅我开了10倍还是RE
#include <bits/stdc++.h>
#define fp(i, l, r) for(register int i =(l); i <= (r); ++i)
#define fd(i, l, r) for(register int i =(l); i >= (r); --i)
#define ANTISYNC ios::sync_with_stdio(false)
#define full(a, b) memset(a, b, sizeof(a))
#define GIVENTIE cin.tie(0); cout.tie(0)
#define MAXN (int)2e6 + 5
#define ll long long
#define il inline
#define SAFE 4
using namespace std;
template <typename T> il void read(T &dig) {
char c = getchar();
bool flag = false;
dig = 0;
while(!isdigit(c) && c != '-') c = getchar();
if(c == '-') flag = true, c = getchar();
while(isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
if(flag) dig = -dig;
}
int n, m;
int tree[MAXN * 10], num[MAXN * 10];
namespace Segment {
il int ls(int node) {return node << 1;}
il int rs(int node) {return node << 1 | 1;}
il int build(int node, int l, int r) {
if(l == r) {
tree[node] = num[l];
return 0;
}
int mid = (l+r) >> 1;
build(ls(node), l, mid);
build(rs(node), mid+1, r);
tree[node] = min(tree[ls(node)], tree[rs(node)]);
return 0;
}
il int query(int node, int wantl, int wantr, int nowl, int nowr) {
int ret = INT_MAX;
if(wantl <= nowl && nowr <= wantr) {
return tree[node];
}
int mid = (nowl+nowr) >> 1;
if(wantl <= mid) ret = min(ret, query(ls(node), wantl, wantr, nowl, mid));
if(wantr > mid) ret = min(ret, query(rs(node), wantl, wantr, mid+1, nowr));
return ret;
}
};
using namespace Segment;
il int init() {
read(n), read(m);
fp(i, 1, n) read(num[i]);
build(1, 1, n);
printf("0\n");
fp(i, 2, n) {
if(i <= m+1) {
printf("%d\n", query(1, 1, i-1, 1, n));
} else printf("%d\n", query(1, i-m, i-1, 1, n));
}
return 0;
}
int main() {
init();
return 0;
}
优雅的
by 引领天下 @ 2018-08-24 16:08:15
@Fraciton 我怀疑您是数组太大了所以RE了……新人就写namespace?新人就做线段树?新人就红了?
by A星际穿越 @ 2018-08-24 16:09:20
洛谷初学OI就红名吊打大佬系列
by Fraction @ 2018-08-24 16:09:35
@引领天下
by A星际穿越 @ 2018-08-24 16:11:37
重构代码吧这是最快的调代码方式