「Test」全连

考试的时候想到了线段树，但时间不够就随手打了打，超时了

晚上去厕所的时候想了一下，发现自己傻逼了。。

在维护左端点的时候用堆维护一下就好了。

我居然傻乎乎的写了考试的时候那种 ZZ 做法。。

代码： 

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#pragma GCC optimize(3)
#include <bits/stdc++.h>

// Defination {{{
#define PI std::pair<long long, int>
#define mk std::make_pair
#define reg register
#define ll long long
#define rep(i, a, b) for(reg int i = a; i <= b; ++i)
#define per(i, a, b) for(reg int i = a; i >= b; --i)
#define pb push_back
#define debug(...) fprintf(stderr, __VA_ARGS__)
// }}}

template<typename T> T max(T a, T b) { return a > b ? a : b; }
template<typename T> T min(T a, T b) { return a < b ? a : b; }

template<typename T> void read(T &x) {
    x = 0; reg char ch = getchar(); reg int f = 1;
    for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
    for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
    x *= f;
}

#define N 1000005

int n;
ll t[N], a[N];
ll f[N << 1];

class SegmentTree {
public:
    PI tree[N << 2];

    void pushup(int x) {
        if (tree[x << 1].first > tree[x << 1 | 1].first) tree[x] = tree[x << 1];
        else tree[x] = tree[x << 1 | 1];
    }

    void modify(int l, int r, int pos, ll val, int x) {
        if (l == r) return tree[x].first = val, tree[x].second = l, void();
        reg int mid = l + r >> 1;
        if (pos <= mid) modify(l, mid, pos, val, x << 1);
        else modify(mid + 1, r, pos, val, x << 1 | 1);
        pushup(x);
    }

    PI query(int l, int r, int la, int ra, int x) {
        if (l >= la && r <= ra) return tree[x];
        int mid = l + r >> 1;
        PI res;
        res.first = -LLONG_MAX;
        res.second = 0;
        if (la <= mid) res = query(l, mid, la, ra, x << 1);
        if (ra > mid) {
            PI tmp = query(mid + 1, r, la, ra, x << 1 | 1);
            if (tmp.first >= res.first) res = tmp;
        }
        return res;
    }

    void build(int l, int r, int x) {
        if (l == r) return tree[x].first = -LLONG_MAX, tree[x].second = 0, void();
        reg int mid = l + r >> 1;
        build(l, mid, x << 1);
        build(mid + 1, r, x << 1 | 1);
        pushup(x);
    }
} seg;

int tot; 
int tf[N];

std::priority_queue<PI> q;
 
int main() {
    freopen ("fc.in", "r", stdin);
    freopen ("fc.out", "w", stdout);
    read(n);
    seg.build(1, n, 1);
    rep (i, 1, n) read(t[i]);
    rep (i, 1, n) read(a[i]), a[i] = a[i] * t[i];
    per (i, n, 1) {
        while (!q.empty() && q.top().first >= i) {
            reg PI tmp = q.top();
            q.pop();
            seg.modify(1, n, tmp.second, f[tmp.second], 1);
        }
        reg int pos = i + t[i];
        if (pos > n) f[i] = a[i];
        else {
            reg PI tmp = seg.query(1, n, pos, n, 1);
            if (tmp.first == -LLONG_MAX) {
                f[i] = a[i];
                q.push(mk(i - t[i], i));
                continue;
            }
            reg int id = tmp.second;
            if (id - t[id] < i) {
                tf[++tot] = id;
                seg.modify(1, n, id, -LLONG_MAX, 1);
            } else {
                f[i] = f[id] + a[i];
            }
        }
        q.push(mk(i - t[i], i));
    }
    ll ans = 0;
    rep (i, 1, n) {
        ans = max(ans, f[i]);
    }
    printf("%lld\n", ans);
    return 0; 
}


/*
 _____  ____    _____
|__  / |  _ \  |__  /
  / /  | |_) |   / / 
 / /_  |  _ <   / /_ 
/____| |_| \_\ /____|
  

 ______________________________________ 
< fc.cpp is created by zrz who is weak >
 -------------------------------------- 
        \   ^__^
         \  (^^)\_______
            (__)\       )\/\
             U ||----w |
                ||     ||

*/

赏

谢谢你请我吃薯片

扫一扫，分享到微信

微信分享二维码