oj.uz

답안 #262434

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
262434 2020-08-12T22:51:23 Z doowey Two Antennas (JOI19_antennas) C++14
100 / 100
 1254 ms 93108 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)4e5 + 100;
const ll inf = (ll)1e16;
vector<int> add[N], rem[N];
int H[N], A[N], B[N];

struct Node{
    ll lazy;
    ll mxa;
    ll res;
};

Node T[N * 4];

void init(){
    for(int i = 0 ; i < N * 4; i ++ ){
        T[i] = {-inf, -inf, -inf};
    }
}

void push(int node, int cl, int cr){
    T[node].res = max(T[node].res, T[node].mxa + T[node].lazy);
    if(cl != cr){
        T[node * 2].lazy = max(T[node * 2].lazy, T[node].lazy);
        T[node * 2 + 1].lazy = max(T[node * 2 + 1].lazy, T[node].lazy);
    }
    T[node].lazy = -inf;
}

void setv(int node, int cl, int cr, int pos, ll vl){
    push(node, cl, cr);
    if(cl == cr){
        T[node].mxa = vl;
        T[node].res = max(T[node].res, T[node].mxa + T[node].lazy);
        return;
    }
    int mid = (cl + cr) / 2;
    if(mid >= pos){
        setv(node * 2, cl, mid, pos, vl);
    }
    else{
        setv(node * 2 + 1, mid + 1, cr, pos, vl);
    }
    T[node].res = max({T[node].res, T[node * 2].res, T[node * 2 + 1].res});
    T[node].mxa = max(T[node * 2].mxa, T[node * 2 + 1].mxa);
}

ll get(int node, int cl, int cr, int tl, int tr){
    push(node, cl, cr);
    if(cr < tl || cl > tr)
        return -inf;
    if(cl >= tl && cr <= tr)
        return T[node].res;
    int mid = (cl + cr) / 2;
    return max(get(node * 2, cl, mid, tl, tr), get(node * 2 + 1, mid + 1, cr, tl, tr));
}

void upd(int node, int cl, int cr, int tl, int tr, ll vl){
    push(node, cl, cr);
    if(cr < tl || cl > tr)
        return;
    if(cl >= tl && cr <= tr){
        T[node].lazy = vl;
        push(node, cl, cr);
        return;
    }
    int mid = (cl + cr) / 2;
    upd(node * 2, cl, mid, tl, tr, vl);
    upd(node * 2 + 1, mid + 1, cr, tl, tr, vl);
    T[node].res = max({T[node].res, T[node * 2].res, T[node * 2 + 1].res});
}

int n;
int L[N], R[N];
vector<int> iq[N];
ll answ[N];
void solve(){
    init();
    int ni, nj;
    for(int i = 1; i <= n; i ++ ){
        for(auto x  : add[i]){
            setv(1, 1, n, x, -H[x]);
        }
        ni = max(1, i - B[i]);
        nj = max(0, i - A[i]);
        upd(1, 1, n, ni, nj, H[i]);
        for(auto x : iq[i]){
            answ[x] = max(answ[x], get(1, 1, n, L[x], R[x]));
        }
        for(auto x : rem[i]){
            setv(1, 1, n, x, -inf);
        }
    }

}

int main(){
    fastIO;
    cin >> n;
    for(int i = 1; i <= n; i ++ ){
        cin >> H[i] >> A[i] >> B[i];
        add[i + A[i]].push_back(i);
        rem[i + B[i]].push_back(i);
    }
    int q;
    cin >> q;
    for(int i = 1; i <= q; i ++ ){
        cin >> L[i] >> R[i];
        iq[R[i]].push_back(i);
        answ[i] = -inf;
    }
    solve();
    for(int i = 1; i <= n; i ++ )
        H[i] = -H[i];
    solve();
    for(int i = 1; i <= q; i ++ ){
        if(answ[i] < 0)
            answ[i] = -1;
        cout << answ[i] << "\n";
    }
    return 0;
}

Subtask #1
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 46 ms 66296 KB Output is correct
2 Correct 43 ms 66168 KB Output is correct
3 Correct 48 ms 66168 KB Output is correct
4 Correct 44 ms 66296 KB Output is correct
5 Correct 45 ms 66168 KB Output is correct
6 Correct 45 ms 66168 KB Output is correct
7 Correct 44 ms 66168 KB Output is correct
8 Correct 44 ms 66168 KB Output is correct
9 Correct 43 ms 66168 KB Output is correct
10 Correct 45 ms 66168 KB Output is correct
11 Correct 43 ms 66168 KB Output is correct
12 Correct 45 ms 66168 KB Output is correct
13 Correct 45 ms 66176 KB Output is correct
14 Correct 44 ms 66168 KB Output is correct
15 Correct 45 ms 66124 KB Output is correct
16 Correct 44 ms 66168 KB Output is correct
17 Correct 44 ms 66176 KB Output is correct
18 Correct 44 ms 66168 KB Output is correct
19 Correct 44 ms 66168 KB Output is correct
20 Correct 44 ms 66168 KB Output is correct
21 Correct 45 ms 66168 KB Output is correct
22 Correct 43 ms 66168 KB Output is correct
23 Correct 43 ms 66176 KB Output is correct
24 Correct 45 ms 66168 KB Output is correct

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 46 ms 66296 KB Output is correct
2 Correct 43 ms 66168 KB Output is correct
3 Correct 48 ms 66168 KB Output is correct
4 Correct 44 ms 66296 KB Output is correct
5 Correct 45 ms 66168 KB Output is correct
6 Correct 45 ms 66168 KB Output is correct
7 Correct 44 ms 66168 KB Output is correct
8 Correct 44 ms 66168 KB Output is correct
9 Correct 43 ms 66168 KB Output is correct
10 Correct 45 ms 66168 KB Output is correct
11 Correct 43 ms 66168 KB Output is correct
12 Correct 45 ms 66168 KB Output is correct
13 Correct 45 ms 66176 KB Output is correct
14 Correct 44 ms 66168 KB Output is correct
15 Correct 45 ms 66124 KB Output is correct
16 Correct 44 ms 66168 KB Output is correct
17 Correct 44 ms 66176 KB Output is correct
18 Correct 44 ms 66168 KB Output is correct
19 Correct 44 ms 66168 KB Output is correct
20 Correct 44 ms 66168 KB Output is correct
21 Correct 45 ms 66168 KB Output is correct
22 Correct 43 ms 66168 KB Output is correct
23 Correct 43 ms 66176 KB Output is correct
24 Correct 45 ms 66168 KB Output is correct
25 Correct 190 ms 71804 KB Output is correct
26 Correct 61 ms 66936 KB Output is correct
27 Correct 255 ms 74104 KB Output is correct
28 Correct 270 ms 74264 KB Output is correct
29 Correct 182 ms 71800 KB Output is correct
30 Correct 195 ms 71548 KB Output is correct
31 Correct 202 ms 73592 KB Output is correct
32 Correct 263 ms 74360 KB Output is correct
33 Correct 271 ms 73720 KB Output is correct
34 Correct 151 ms 70136 KB Output is correct
35 Correct 275 ms 74104 KB Output is correct
36 Correct 280 ms 74236 KB Output is correct
37 Correct 168 ms 70268 KB Output is correct
38 Correct 273 ms 73336 KB Output is correct
39 Correct 76 ms 67196 KB Output is correct
40 Correct 273 ms 73336 KB Output is correct
41 Correct 235 ms 71288 KB Output is correct
42 Correct 269 ms 73340 KB Output is correct
43 Correct 114 ms 68600 KB Output is correct
44 Correct 268 ms 73208 KB Output is correct
45 Correct 90 ms 67728 KB Output is correct
46 Correct 270 ms 73268 KB Output is correct
47 Correct 99 ms 68088 KB Output is correct
48 Correct 274 ms 73336 KB Output is correct

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 552 ms 80632 KB Output is correct
2 Correct 572 ms 82168 KB Output is correct
3 Correct 384 ms 77432 KB Output is correct
4 Correct 592 ms 82040 KB Output is correct
5 Correct 241 ms 73340 KB Output is correct
6 Correct 597 ms 82168 KB Output is correct
7 Correct 487 ms 79992 KB Output is correct
8 Correct 576 ms 82168 KB Output is correct
9 Correct 99 ms 68600 KB Output is correct
10 Correct 570 ms 82168 KB Output is correct
11 Correct 330 ms 76024 KB Output is correct
12 Correct 572 ms 82296 KB Output is correct
13 Correct 431 ms 78664 KB Output is correct
14 Correct 415 ms 77984 KB Output is correct
15 Correct 436 ms 78696 KB Output is correct
16 Correct 325 ms 79408 KB Output is correct
17 Correct 464 ms 78452 KB Output is correct
18 Correct 403 ms 78328 KB Output is correct
19 Correct 415 ms 78284 KB Output is correct
20 Correct 392 ms 78404 KB Output is correct
21 Correct 414 ms 78300 KB Output is correct
22 Correct 419 ms 78452 KB Output is correct
23 Correct 412 ms 78324 KB Output is correct
24 Correct 329 ms 78964 KB Output is correct

Subtask #4
65.0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 46 ms 66296 KB Output is correct
2 Correct 43 ms 66168 KB Output is correct
3 Correct 48 ms 66168 KB Output is correct
4 Correct 44 ms 66296 KB Output is correct
5 Correct 45 ms 66168 KB Output is correct
6 Correct 45 ms 66168 KB Output is correct
7 Correct 44 ms 66168 KB Output is correct
8 Correct 44 ms 66168 KB Output is correct
9 Correct 43 ms 66168 KB Output is correct
10 Correct 45 ms 66168 KB Output is correct
11 Correct 43 ms 66168 KB Output is correct
12 Correct 45 ms 66168 KB Output is correct
13 Correct 45 ms 66176 KB Output is correct
14 Correct 44 ms 66168 KB Output is correct
15 Correct 45 ms 66124 KB Output is correct
16 Correct 44 ms 66168 KB Output is correct
17 Correct 44 ms 66176 KB Output is correct
18 Correct 44 ms 66168 KB Output is correct
19 Correct 44 ms 66168 KB Output is correct
20 Correct 44 ms 66168 KB Output is correct
21 Correct 45 ms 66168 KB Output is correct
22 Correct 43 ms 66168 KB Output is correct
23 Correct 43 ms 66176 KB Output is correct
24 Correct 45 ms 66168 KB Output is correct
25 Correct 190 ms 71804 KB Output is correct
26 Correct 61 ms 66936 KB Output is correct
27 Correct 255 ms 74104 KB Output is correct
28 Correct 270 ms 74264 KB Output is correct
29 Correct 182 ms 71800 KB Output is correct
30 Correct 195 ms 71548 KB Output is correct
31 Correct 202 ms 73592 KB Output is correct
32 Correct 263 ms 74360 KB Output is correct
33 Correct 271 ms 73720 KB Output is correct
34 Correct 151 ms 70136 KB Output is correct
35 Correct 275 ms 74104 KB Output is correct
36 Correct 280 ms 74236 KB Output is correct
37 Correct 168 ms 70268 KB Output is correct
38 Correct 273 ms 73336 KB Output is correct
39 Correct 76 ms 67196 KB Output is correct
40 Correct 273 ms 73336 KB Output is correct
41 Correct 235 ms 71288 KB Output is correct
42 Correct 269 ms 73340 KB Output is correct
43 Correct 114 ms 68600 KB Output is correct
44 Correct 268 ms 73208 KB Output is correct
45 Correct 90 ms 67728 KB Output is correct
46 Correct 270 ms 73268 KB Output is correct
47 Correct 99 ms 68088 KB Output is correct
48 Correct 274 ms 73336 KB Output is correct
49 Correct 552 ms 80632 KB Output is correct
50 Correct 572 ms 82168 KB Output is correct
51 Correct 384 ms 77432 KB Output is correct
52 Correct 592 ms 82040 KB Output is correct
53 Correct 241 ms 73340 KB Output is correct
54 Correct 597 ms 82168 KB Output is correct
55 Correct 487 ms 79992 KB Output is correct
56 Correct 576 ms 82168 KB Output is correct
57 Correct 99 ms 68600 KB Output is correct
58 Correct 570 ms 82168 KB Output is correct
59 Correct 330 ms 76024 KB Output is correct
60 Correct 572 ms 82296 KB Output is correct
61 Correct 431 ms 78664 KB Output is correct
62 Correct 415 ms 77984 KB Output is correct
63 Correct 436 ms 78696 KB Output is correct
64 Correct 325 ms 79408 KB Output is correct
65 Correct 464 ms 78452 KB Output is correct
66 Correct 403 ms 78328 KB Output is correct
67 Correct 415 ms 78284 KB Output is correct
68 Correct 392 ms 78404 KB Output is correct
69 Correct 414 ms 78300 KB Output is correct
70 Correct 419 ms 78452 KB Output is correct
71 Correct 412 ms 78324 KB Output is correct
72 Correct 329 ms 78964 KB Output is correct
73 Correct 922 ms 88824 KB Output is correct
74 Correct 605 ms 83064 KB Output is correct
75 Correct 872 ms 87672 KB Output is correct
76 Correct 1155 ms 93048 KB Output is correct
77 Correct 592 ms 80808 KB Output is correct
78 Correct 990 ms 89720 KB Output is correct
79 Correct 1031 ms 90744 KB Output is correct
80 Correct 1254 ms 93100 KB Output is correct
81 Correct 474 ms 77432 KB Output is correct
82 Correct 897 ms 87928 KB Output is correct
83 Correct 881 ms 86264 KB Output is correct
84 Correct 1147 ms 93108 KB Output is correct
85 Correct 755 ms 84752 KB Output is correct
86 Correct 948 ms 87968 KB Output is correct
87 Correct 482 ms 80376 KB Output is correct
88 Correct 895 ms 89152 KB Output is correct
89 Correct 834 ms 85752 KB Output is correct
90 Correct 944 ms 87928 KB Output is correct
91 Correct 601 ms 82128 KB Output is correct
92 Correct 971 ms 88004 KB Output is correct
93 Correct 516 ms 80284 KB Output is correct
94 Correct 998 ms 88436 KB Output is correct
95 Correct 555 ms 81268 KB Output is correct
96 Correct 902 ms 88820 KB Output is correct