oj.uz

Submission #392808

# Submission time Handle Problem Language Result Execution time Memory
392808 2021-04-21T18:25:16 Z vaaven Two Antennas (JOI19_antennas) C++14
100 / 100
 1344 ms 59480 KB 
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <set>
#include <stack>
#include <iomanip>
#include <bitset>
#include <map>
#include <cassert>
#include <array>
#include <queue>
#include <cstring>
#include <random>
#include <unordered_set>
#include <unordered_map>
#define pqueue priority_queue
#define pb(x) push_back(x)
// #define endl '\n'
#define all(x) x.begin(), x.end()
#define int long  long
  
using namespace std;
  
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
// typedef tuple<ll, ll, ll> tiii;
typedef pair<int, int> pii;
typedef vector<pair<int, int> > vpii;
typedef vector<bool> vb;
typedef vector<string> vs;
typedef vector<char> vc;
  
const int inf = 1e9 + 228;
const int infll = 1e18;
const ll mod = 1e9 + 7;
const ll mod2 = 998244353;
const ld eps = 1e-14;
  
  
void fast_io(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
//    freopen("inputik.txt", "r", stdin);
//    freopen("outputik.txt", "w", stdout);
}
 
const int maxn = 2e5 + 228;
 
int t[maxn*4];
int mx[maxn*4];
int lzupd[maxn*4];
int H[maxn], A[maxn], B[maxn];
int n, q;
int L[maxn], R[maxn];
int ans[maxn];
 
void push(int v, int l, int r){
    if(lzupd[v] != infll){
//        cout << 1 << endl;
//        cout << v << ": " << t[v] << " -> " << t[v] << endl;
        t[v] = max(t[v], mx[v] - lzupd[v]);
        if(l != r){
            lzupd[v*2] = min(lzupd[v*2], lzupd[v]);
            lzupd[v*2+1] = min(lzupd[v*2+1], lzupd[v]);
        }
        lzupd[v] = infll;
    }
}
 
void upd(int v, int l, int r, int k){
    push(v, l, r);
    if(l == r){
        if(mx[v] == -infll){
            mx[v] = H[l];
        } else{
            mx[v] = -infll;
        }
    } else{
        int mid = (l+r)/2;
        if(k <= mid){
            upd(v*2, l, mid, k);
        } else{
            upd(v*2+1, mid+1, r, k);
        }
//        push(v*2, l, mid);
//        push(v*2+1, mid+1, r);
        mx[v] = max(mx[v*2], mx[v*2+1]);
//        t[v] = max(t[v*2], t[v*2+1]);
    }
}
 
void sett(int v, int l, int r, int ql, int qr, int k){
    push(v, l, r);
    if(ql <= l && r <= qr){
        lzupd[v] = min(lzupd[v], k);
        push(v, l, r);
    } else if(ql > r || l > qr){
        return;
    } else{
        int mid = (l+r)/2;
        sett(v*2, l, mid, ql, qr, k);
        sett(v*2+1, mid+1, r, ql, qr, k);
        t[v] = max(t[v*2], t[v*2+1]);
//        mx[v] = max(mx[v*2], mx[v*2+1]);
    }
}
 
int get(int v, int l, int r, int ql, int qr){
    push(v, l, r);
    if(ql <= l && r <= qr){
        return t[v];
    } else if(l > qr || ql > r){
        return -1;
    } else{
        int mid = (l+r)/2;
        return max(get(v*2, l, mid, ql, qr), get(v*2+1, mid+1, r, ql, qr));
    }
//    cout << t[1] << endl;
}
 
void solve2(){
    vvi to_add(n+1);
    vvi to_del(n+1);
    vvi posts(n+1);
    for(int &i:lzupd)
        i = infll;
    for(int &i:t)
        i = -infll;
    for(int &i:mx)
        i = -infll;
    for(int i=0; i<q; i++){
        posts[R[i]].pb(i);
    }
    for(int i=0; i<n; i++){
        if(i + A[i] < n){
            to_add[i + A[i]].pb(i);
            to_del[min(i + B[i] + 1, n)].pb(i);
        }
        for(int j:to_add[i])
            upd(1, 0, maxn, j);
        for(int j:to_del[i])
            upd(1, 0, maxn, j);
        if(i - A[i] >= 0){
            sett(1, 0, maxn, max(i - B[i], 0ll), i - A[i], H[i]);
        }
        for(int j:posts[i]){
//            cout << L[j] << " " << R[j] << " " << get(1, 0, maxn, L[j], R[j]) << endl;
            ans[j] = max(ans[j], get(1, 0, maxn, L[j], R[j]));
        }
    }
}
 
void solve(){
    cin >> n;
    for(int i=0; i<n; i++){
        cin >> H[i] >> A[i] >> B[i];
    }
    for(int &i:ans)
        i = -1;
//    int q;
    cin >> q;
    for(int i=0; i<q; i++){
        cin >> L[i] >> R[i];
        L[i]--, R[i]--;
    }
    solve2();
    for(int &i:H)
        i = -i;
    solve2();
    for(int i=0; i<q; i++)
        cout << ans[i] << endl;
}
/*
5
10 2 4
1 1 1
2 1 3
1 1 1
100 1 1
5
1 2
2 3
1 3
1 4
1 5
=======
 20
 260055884 2 15
 737689751 5 5
 575359903 1 15
 341907415 14 14
 162026576 9 19
 55126745 10 19
 95712405 11 14
 416027186 8 13
 370819848 11 14
 629309664 4 13
 822713895 5 15
 390716905 13 17
 577166133 8 19
 195931195 10 17
 377030463 14 17
 968486685 11 19
 963040581 4 10
 566835557 1 12
 586336111 6 16
 385865831 8 9
 1
 1 20
 */
signed main(){
     fast_io();
//  ;(time(NULL));
    cout << fixed << setprecision(10);
    int q = 1;
//    cin >> q;
    while(q--)
        solve();
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 22220 KB Output is correct
2 Correct 15 ms 22220 KB Output is correct
3 Correct 15 ms 22340 KB Output is correct
4 Correct 16 ms 22312 KB Output is correct
5 Correct 15 ms 22300 KB Output is correct
6 Correct 15 ms 22316 KB Output is correct
7 Correct 15 ms 22288 KB Output is correct
8 Correct 15 ms 22352 KB Output is correct
9 Correct 15 ms 22220 KB Output is correct
10 Correct 17 ms 22264 KB Output is correct
11 Correct 15 ms 22220 KB Output is correct
12 Correct 15 ms 22360 KB Output is correct
13 Correct 16 ms 22196 KB Output is correct
14 Correct 15 ms 22264 KB Output is correct
15 Correct 15 ms 22220 KB Output is correct
16 Correct 15 ms 22296 KB Output is correct
17 Correct 15 ms 22332 KB Output is correct
18 Correct 17 ms 22348 KB Output is correct
19 Correct 15 ms 22348 KB Output is correct
20 Correct 15 ms 22236 KB Output is correct
21 Correct 15 ms 22288 KB Output is correct
22 Correct 17 ms 22296 KB Output is correct
23 Correct 15 ms 22220 KB Output is correct
24 Correct 15 ms 22348 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 22220 KB Output is correct
2 Correct 15 ms 22220 KB Output is correct
3 Correct 15 ms 22340 KB Output is correct
4 Correct 16 ms 22312 KB Output is correct
5 Correct 15 ms 22300 KB Output is correct
6 Correct 15 ms 22316 KB Output is correct
7 Correct 15 ms 22288 KB Output is correct
8 Correct 15 ms 22352 KB Output is correct
9 Correct 15 ms 22220 KB Output is correct
10 Correct 17 ms 22264 KB Output is correct
11 Correct 15 ms 22220 KB Output is correct
12 Correct 15 ms 22360 KB Output is correct
13 Correct 16 ms 22196 KB Output is correct
14 Correct 15 ms 22264 KB Output is correct
15 Correct 15 ms 22220 KB Output is correct
16 Correct 15 ms 22296 KB Output is correct
17 Correct 15 ms 22332 KB Output is correct
18 Correct 17 ms 22348 KB Output is correct
19 Correct 15 ms 22348 KB Output is correct
20 Correct 15 ms 22236 KB Output is correct
21 Correct 15 ms 22288 KB Output is correct
22 Correct 17 ms 22296 KB Output is correct
23 Correct 15 ms 22220 KB Output is correct
24 Correct 15 ms 22348 KB Output is correct
25 Correct 374 ms 27732 KB Output is correct
26 Correct 54 ms 23104 KB Output is correct
27 Correct 527 ms 30492 KB Output is correct
28 Correct 526 ms 30496 KB Output is correct
29 Correct 381 ms 27784 KB Output is correct
30 Correct 357 ms 28404 KB Output is correct
31 Correct 488 ms 29156 KB Output is correct
32 Correct 533 ms 30744 KB Output is correct
33 Correct 489 ms 29360 KB Output is correct
34 Correct 258 ms 26852 KB Output is correct
35 Correct 516 ms 30420 KB Output is correct
36 Correct 531 ms 30836 KB Output is correct
37 Correct 298 ms 27328 KB Output is correct
38 Correct 510 ms 29832 KB Output is correct
39 Correct 82 ms 23620 KB Output is correct
40 Correct 515 ms 29896 KB Output is correct
41 Correct 369 ms 27840 KB Output is correct
42 Correct 511 ms 30000 KB Output is correct
43 Correct 177 ms 25156 KB Output is correct
44 Correct 509 ms 29916 KB Output is correct
45 Correct 100 ms 23856 KB Output is correct
46 Correct 508 ms 29816 KB Output is correct
47 Correct 139 ms 24524 KB Output is correct
48 Correct 511 ms 30032 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 465 ms 45476 KB Output is correct
2 Correct 516 ms 48156 KB Output is correct
3 Correct 344 ms 40552 KB Output is correct
4 Correct 503 ms 47980 KB Output is correct
5 Correct 198 ms 33956 KB Output is correct
6 Correct 498 ms 48024 KB Output is correct
7 Correct 439 ms 44564 KB Output is correct
8 Correct 527 ms 48156 KB Output is correct
9 Correct 62 ms 26280 KB Output is correct
10 Correct 498 ms 48060 KB Output is correct
11 Correct 301 ms 38396 KB Output is correct
12 Correct 503 ms 48168 KB Output is correct
13 Correct 252 ms 46496 KB Output is correct
14 Correct 235 ms 46436 KB Output is correct
15 Correct 226 ms 46244 KB Output is correct
16 Correct 235 ms 46880 KB Output is correct
17 Correct 256 ms 46464 KB Output is correct
18 Correct 243 ms 46780 KB Output is correct
19 Correct 242 ms 46368 KB Output is correct
20 Correct 231 ms 46524 KB Output is correct
21 Correct 231 ms 46960 KB Output is correct
22 Correct 237 ms 46408 KB Output is correct
23 Correct 238 ms 46116 KB Output is correct
24 Correct 224 ms 46224 KB Output is correct

Subtask #4
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 22220 KB Output is correct
2 Correct 15 ms 22220 KB Output is correct
3 Correct 15 ms 22340 KB Output is correct
4 Correct 16 ms 22312 KB Output is correct
5 Correct 15 ms 22300 KB Output is correct
6 Correct 15 ms 22316 KB Output is correct
7 Correct 15 ms 22288 KB Output is correct
8 Correct 15 ms 22352 KB Output is correct
9 Correct 15 ms 22220 KB Output is correct
10 Correct 17 ms 22264 KB Output is correct
11 Correct 15 ms 22220 KB Output is correct
12 Correct 15 ms 22360 KB Output is correct
13 Correct 16 ms 22196 KB Output is correct
14 Correct 15 ms 22264 KB Output is correct
15 Correct 15 ms 22220 KB Output is correct
16 Correct 15 ms 22296 KB Output is correct
17 Correct 15 ms 22332 KB Output is correct
18 Correct 17 ms 22348 KB Output is correct
19 Correct 15 ms 22348 KB Output is correct
20 Correct 15 ms 22236 KB Output is correct
21 Correct 15 ms 22288 KB Output is correct
22 Correct 17 ms 22296 KB Output is correct
23 Correct 15 ms 22220 KB Output is correct
24 Correct 15 ms 22348 KB Output is correct
25 Correct 374 ms 27732 KB Output is correct
26 Correct 54 ms 23104 KB Output is correct
27 Correct 527 ms 30492 KB Output is correct
28 Correct 526 ms 30496 KB Output is correct
29 Correct 381 ms 27784 KB Output is correct
30 Correct 357 ms 28404 KB Output is correct
31 Correct 488 ms 29156 KB Output is correct
32 Correct 533 ms 30744 KB Output is correct
33 Correct 489 ms 29360 KB Output is correct
34 Correct 258 ms 26852 KB Output is correct
35 Correct 516 ms 30420 KB Output is correct
36 Correct 531 ms 30836 KB Output is correct
37 Correct 298 ms 27328 KB Output is correct
38 Correct 510 ms 29832 KB Output is correct
39 Correct 82 ms 23620 KB Output is correct
40 Correct 515 ms 29896 KB Output is correct
41 Correct 369 ms 27840 KB Output is correct
42 Correct 511 ms 30000 KB Output is correct
43 Correct 177 ms 25156 KB Output is correct
44 Correct 509 ms 29916 KB Output is correct
45 Correct 100 ms 23856 KB Output is correct
46 Correct 508 ms 29816 KB Output is correct
47 Correct 139 ms 24524 KB Output is correct
48 Correct 511 ms 30032 KB Output is correct
49 Correct 465 ms 45476 KB Output is correct
50 Correct 516 ms 48156 KB Output is correct
51 Correct 344 ms 40552 KB Output is correct
52 Correct 503 ms 47980 KB Output is correct
53 Correct 198 ms 33956 KB Output is correct
54 Correct 498 ms 48024 KB Output is correct
55 Correct 439 ms 44564 KB Output is correct
56 Correct 527 ms 48156 KB Output is correct
57 Correct 62 ms 26280 KB Output is correct
58 Correct 498 ms 48060 KB Output is correct
59 Correct 301 ms 38396 KB Output is correct
60 Correct 503 ms 48168 KB Output is correct
61 Correct 252 ms 46496 KB Output is correct
62 Correct 235 ms 46436 KB Output is correct
63 Correct 226 ms 46244 KB Output is correct
64 Correct 235 ms 46880 KB Output is correct
65 Correct 256 ms 46464 KB Output is correct
66 Correct 243 ms 46780 KB Output is correct
67 Correct 242 ms 46368 KB Output is correct
68 Correct 231 ms 46524 KB Output is correct
69 Correct 231 ms 46960 KB Output is correct
70 Correct 237 ms 46408 KB Output is correct
71 Correct 238 ms 46116 KB Output is correct
72 Correct 224 ms 46224 KB Output is correct
73 Correct 1070 ms 52572 KB Output is correct
74 Correct 589 ms 49068 KB Output is correct
75 Correct 1148 ms 49636 KB Output is correct
76 Correct 1344 ms 57748 KB Output is correct
77 Correct 746 ms 42080 KB Output is correct
78 Correct 1061 ms 56052 KB Output is correct
79 Correct 1229 ms 54244 KB Output is correct
80 Correct 1300 ms 59480 KB Output is correct
81 Correct 669 ms 35980 KB Output is correct
82 Correct 932 ms 53896 KB Output is correct
83 Correct 1063 ms 49188 KB Output is correct
84 Correct 1328 ms 57592 KB Output is correct
85 Correct 686 ms 52688 KB Output is correct
86 Correct 971 ms 56828 KB Output is correct
87 Correct 331 ms 47912 KB Output is correct
88 Correct 989 ms 57056 KB Output is correct
89 Correct 804 ms 54152 KB Output is correct
90 Correct 977 ms 56956 KB Output is correct
91 Correct 491 ms 49988 KB Output is correct
92 Correct 962 ms 56008 KB Output is correct
93 Correct 361 ms 49000 KB Output is correct
94 Correct 988 ms 56696 KB Output is correct
95 Correct 440 ms 49056 KB Output is correct
96 Correct 966 ms 56352 KB Output is correct