| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
不知道哪里有问题囧?#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <deque>
using namespace std;
const int maxn = 1000010;
int n, L, A, B, s, e, c[maxn], f[maxn];
deque<int> que;
int main() {
while (~scanf("%d%d%d%d", &n, &L, &A, &B)) {
memset(f, -1, sizeof(f));
f[0] = 0;
memset(c, 0, sizeof(c));
while (n --) {
scanf("%d%d", &s, &e);
c[s+1] ++, c[e] --;
}
for (int i = 1; i <= L; i ++) c[i] += c[i-1];
while (!que.empty()) que.pop_back();
int j = 0;
for (int i = 1; i <= L; i ++) {
if (c[i]) continue;
for (; j <= i-2*A; j ++) {
if (j < i-2*B || f[j] == -1) continue;
while (!que.empty() && f[que.back()] >= f[j]) que.pop_back();
que.push_back(j);
while (!que.empty() && que.front() < i-2*B) que.pop_front();
}
if (!que.empty()) {
f[i] = f[que.front()] + 1;
}
}
printf("%d\n", f[L]);
}
return 0;
}
/**
2 8
1 2
6 7
3 6
*/
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator