Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

不知道哪里有问题囧?

Posted by quanjun at 2020-02-06 20:53:00 on Problem 2373
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator