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