VIJOS1782 - [NOIP2012]借教室

2016/11/10

一周多没写是因为期中考试。(然而这货炸了)

周末 LMJ 大佬讲了下区间问题的各种技巧,然后有提到这道题。

思路

LMJ 原话:这个题卡线段树的常数,我们考虑到线段树的那个 log 太大了,那么什么东西的 log 小呢————二分答案。于是用二分答案做(开始倒差分验证的公式)

↑就是这样, 时间二分答案,差分之后在 内验证解。总体复杂度

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <bits/stdc++.h>
#ifndef LCYTEST
#   define release(_x) { _x }
#else
#   define release(_x) ;
#endif
using namespace std;
const int PSIZ = 1E6;
typedef pair<int, int> PII;

struct task {
    int r, l, w;
} T[PSIZ];
int P[PSIZ];
int N, M;

bool solve(int L) { // [0, L]
    static int D[PSIZ];
    memset(D, 0, sizeof(D));
    for(int i=0;i<=L;i++) { D[T[i].l] += T[i].w; D[T[i].r+1] -= T[i].w; }
    int sum = 0;
    for(int i=0;i<N;i++) { sum += D[i]; if(sum > P[i]) { return false; } }
    return true;
}

int main() {
    release({
        ios::sync_with_stdio(false); cin.tie(NULL);
    });

    cin >> N >> M;
    for(int i=0;i<N;i++) cin >> P[i];
    for(int i=0;i<M;i++) { cin >> T[i].w >> T[i].l >> T[i].r; T[i].l--; T[i].r--; }

    int L = 0, R = M;
    while(L < R-1) { // [L, R)
        int Mid = (L + R) >> 1;
        //cout << Mid << " " << L << " " << R << endl;

        if(solve(Mid)) {
            L = Mid;
        } else {
            R = Mid;
        }
    }

    if(!solve(0)) return cout << "-1" << endl <<"1" << endl, 0; // 这种情况没法做,要特判

    if(solve(R)) cout << "0" << endl;
    else cout << "-1" << endl << R+1 << endl;
}