oj.uz

Submission #210733

# Submission time Handle Problem Language Result Execution time Memory
210733 2020-03-18T07:50:55 Z mhy908 Two Antennas (JOI19_antennas) C++14
100 / 100
 847 ms 54748 KB 
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sortvec(x) sort(all(x))
#define compress(x) x.erase(unique(all(x)), x.end())
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
typedef pair<int, LL> pil;
typedef pair<LL, int> pli;
const LL llinf=987654321987654321;
const int inf=2000000000;

struct SEGMENT_TREE{
    LL tree[800010], h[800010], lazy[800010];
    void init(){
        for(int i=1; i<800000; i++){
            tree[i]=lazy[i]=-llinf;
            h[i]=llinf;
        }
    }
    void propogate(int point){
        lazy[point*2]=max(lazy[point], lazy[point*2]);
        lazy[point*2+1]=max(lazy[point], lazy[point*2+1]);
        tree[point*2]=max(tree[point*2], lazy[point*2]-h[point*2]);
        tree[point*2+1]=max(tree[point*2+1], lazy[point*2+1]-h[point*2+1]);
        lazy[point]=-llinf;
    }
    void update(int point, int s, int e, int num, LL qu){
        if(s==e){
            h[point]=qu;
            lazy[point]=-llinf;
            return;
        }
        propogate(point);
        int mid=(s+e)/2;
        if(num<=mid)update(point*2, s, mid, num, qu);
        else update(point*2+1, mid+1, e, num, qu);
        tree[point]=max(tree[point*2], tree[point*2+1]);
        h[point]=min(h[point*2], h[point*2+1]);
    }
    void alter(int point, int s, int e, int a, int b, LL qu){
        if(e<a||s>b)return;
        if(a<=s&&e<=b){
            lazy[point]=max(lazy[point], qu);
            tree[point]=max(tree[point], qu-h[point]);
            return;
        }
        int mid=(s+e)/2;
        propogate(point);
        alter(point*2, s, mid, a, b, qu);
        alter(point*2+1, mid+1, e, a, b, qu);
        tree[point]=max(tree[point*2], tree[point*2+1]);
    }
    LL query(int point, int s, int e, int a, int b){
        if(e<a||s>b)return -llinf;
        if(a<=s&&e<=b)return tree[point];
        propogate(point);
        int mid=(s+e)/2;
        return max(query(point*2, s, mid, a, b), query(point*2+1, mid+1, e, a, b));
    }
}seg;

int n, q;
pii range[200010];
pii query[200010];
LL ans[200010], h[200010];

vector<pii> qu[200010], upd[200010];
void solve(){
    for(int i=1; i<=n; i++){
        qu[i].clear();
        upd[i].clear();
    }
    seg.init();
    for(int i=1; i<=n; i++){
        int t1=min(i+range[i].F, n+1);
        int t2=min(i+range[i].S, n)+1;
        upd[t1].pb(mp(i, 1));
        upd[t2].pb(mp(i, 0));
    }
    for(int i=1; i<=q; i++)qu[query[i].S].pb(mp(query[i].F, i));
    for(int i=1; i<=n; i++){
        for(auto j:upd[i]){
            if(j.S)seg.update(1, 1, n, j.F, h[j.F]);
            else seg.update(1, 1, n, j.F, llinf);
        }
        if(i-range[i].F>=1){
            seg.alter(1, 1, n, max(1, i-range[i].S), i-range[i].F, h[i]);
        }
        for(auto j:qu[i]){
            //printf("query %d : %lld\n", j.S, seg.query(1, 1, n, j.F, i));
            ans[j.S]=max(ans[j.S], seg.query(1, 1, n, j.F, i));
        }
    }
}
int main(){
    scanf("%d", &n);
    for(int i=1; i<=n; i++){
        scanf("%lld %d %d", &h[i], &range[i].F, &range[i].S);
    }
    scanf("%d", &q);
    for(int i=1; i<=q; i++){
        scanf("%d %d", &query[i].F, &query[i].S);
        ans[i]=-1;
    }
    solve();
    for(int i=1; i<=n; i++)h[i]=1000000000-h[i];
    solve();
    for(int i=1; i<=q; i++)printf("%lld\n", ans[i]);
}

Compilation message

antennas.cpp: In function 'int main()':
antennas.cpp:102:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
antennas.cpp:104:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld %d %d", &h[i], &range[i].F, &range[i].S);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:106:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &q);
     ~~~~~^~~~~~~~~~
antennas.cpp:108:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &query[i].F, &query[i].S);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 28536 KB Output is correct
2 Correct 24 ms 28536 KB Output is correct
3 Correct 23 ms 28540 KB Output is correct
4 Correct 23 ms 28536 KB Output is correct
5 Correct 22 ms 28536 KB Output is correct
6 Correct 22 ms 28536 KB Output is correct
7 Correct 22 ms 28536 KB Output is correct
8 Correct 22 ms 28536 KB Output is correct
9 Correct 23 ms 28536 KB Output is correct
10 Correct 22 ms 28536 KB Output is correct
11 Correct 22 ms 28536 KB Output is correct
12 Correct 23 ms 28536 KB Output is correct
13 Correct 22 ms 28536 KB Output is correct
14 Correct 23 ms 28536 KB Output is correct
15 Correct 22 ms 28536 KB Output is correct
16 Correct 22 ms 28536 KB Output is correct
17 Correct 22 ms 28536 KB Output is correct
18 Correct 23 ms 28536 KB Output is correct
19 Correct 22 ms 28536 KB Output is correct
20 Correct 23 ms 28536 KB Output is correct
21 Correct 23 ms 28536 KB Output is correct
22 Correct 22 ms 28536 KB Output is correct
23 Correct 23 ms 28556 KB Output is correct
24 Correct 22 ms 28556 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 28536 KB Output is correct
2 Correct 24 ms 28536 KB Output is correct
3 Correct 23 ms 28540 KB Output is correct
4 Correct 23 ms 28536 KB Output is correct
5 Correct 22 ms 28536 KB Output is correct
6 Correct 22 ms 28536 KB Output is correct
7 Correct 22 ms 28536 KB Output is correct
8 Correct 22 ms 28536 KB Output is correct
9 Correct 23 ms 28536 KB Output is correct
10 Correct 22 ms 28536 KB Output is correct
11 Correct 22 ms 28536 KB Output is correct
12 Correct 23 ms 28536 KB Output is correct
13 Correct 22 ms 28536 KB Output is correct
14 Correct 23 ms 28536 KB Output is correct
15 Correct 22 ms 28536 KB Output is correct
16 Correct 22 ms 28536 KB Output is correct
17 Correct 22 ms 28536 KB Output is correct
18 Correct 23 ms 28536 KB Output is correct
19 Correct 22 ms 28536 KB Output is correct
20 Correct 23 ms 28536 KB Output is correct
21 Correct 23 ms 28536 KB Output is correct
22 Correct 22 ms 28536 KB Output is correct
23 Correct 23 ms 28556 KB Output is correct
24 Correct 22 ms 28556 KB Output is correct
25 Correct 150 ms 35088 KB Output is correct
26 Correct 38 ms 29432 KB Output is correct
27 Correct 195 ms 37624 KB Output is correct
28 Correct 207 ms 37788 KB Output is correct
29 Correct 139 ms 35064 KB Output is correct
30 Correct 139 ms 34680 KB Output is correct
31 Correct 156 ms 36856 KB Output is correct
32 Correct 200 ms 37752 KB Output is correct
33 Correct 183 ms 37112 KB Output is correct
34 Correct 116 ms 33016 KB Output is correct
35 Correct 192 ms 37624 KB Output is correct
36 Correct 201 ms 37752 KB Output is correct
37 Correct 121 ms 33272 KB Output is correct
38 Correct 199 ms 36728 KB Output is correct
39 Correct 48 ms 29816 KB Output is correct
40 Correct 192 ms 36728 KB Output is correct
41 Correct 159 ms 34552 KB Output is correct
42 Correct 194 ms 36728 KB Output is correct
43 Correct 78 ms 31352 KB Output is correct
44 Correct 213 ms 36724 KB Output is correct
45 Correct 54 ms 30072 KB Output is correct
46 Correct 198 ms 36856 KB Output is correct
47 Correct 67 ms 30716 KB Output is correct
48 Correct 202 ms 36728 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 392 ms 38244 KB Output is correct
2 Correct 436 ms 38884 KB Output is correct
3 Correct 277 ms 37092 KB Output is correct
4 Correct 429 ms 38884 KB Output is correct
5 Correct 174 ms 33516 KB Output is correct
6 Correct 439 ms 38884 KB Output is correct
7 Correct 368 ms 38116 KB Output is correct
8 Correct 439 ms 38884 KB Output is correct
9 Correct 65 ms 30576 KB Output is correct
10 Correct 441 ms 38884 KB Output is correct
11 Correct 264 ms 36580 KB Output is correct
12 Correct 431 ms 38884 KB Output is correct
13 Correct 272 ms 37988 KB Output is correct
14 Correct 257 ms 37680 KB Output is correct
15 Correct 251 ms 37700 KB Output is correct
16 Correct 222 ms 38248 KB Output is correct
17 Correct 286 ms 38172 KB Output is correct
18 Correct 258 ms 38076 KB Output is correct
19 Correct 265 ms 37636 KB Output is correct
20 Correct 255 ms 37628 KB Output is correct
21 Correct 248 ms 37084 KB Output is correct
22 Correct 265 ms 37472 KB Output is correct
23 Correct 272 ms 37864 KB Output is correct
24 Correct 235 ms 37820 KB Output is correct

Subtask #4
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 28536 KB Output is correct
2 Correct 24 ms 28536 KB Output is correct
3 Correct 23 ms 28540 KB Output is correct
4 Correct 23 ms 28536 KB Output is correct
5 Correct 22 ms 28536 KB Output is correct
6 Correct 22 ms 28536 KB Output is correct
7 Correct 22 ms 28536 KB Output is correct
8 Correct 22 ms 28536 KB Output is correct
9 Correct 23 ms 28536 KB Output is correct
10 Correct 22 ms 28536 KB Output is correct
11 Correct 22 ms 28536 KB Output is correct
12 Correct 23 ms 28536 KB Output is correct
13 Correct 22 ms 28536 KB Output is correct
14 Correct 23 ms 28536 KB Output is correct
15 Correct 22 ms 28536 KB Output is correct
16 Correct 22 ms 28536 KB Output is correct
17 Correct 22 ms 28536 KB Output is correct
18 Correct 23 ms 28536 KB Output is correct
19 Correct 22 ms 28536 KB Output is correct
20 Correct 23 ms 28536 KB Output is correct
21 Correct 23 ms 28536 KB Output is correct
22 Correct 22 ms 28536 KB Output is correct
23 Correct 23 ms 28556 KB Output is correct
24 Correct 22 ms 28556 KB Output is correct
25 Correct 150 ms 35088 KB Output is correct
26 Correct 38 ms 29432 KB Output is correct
27 Correct 195 ms 37624 KB Output is correct
28 Correct 207 ms 37788 KB Output is correct
29 Correct 139 ms 35064 KB Output is correct
30 Correct 139 ms 34680 KB Output is correct
31 Correct 156 ms 36856 KB Output is correct
32 Correct 200 ms 37752 KB Output is correct
33 Correct 183 ms 37112 KB Output is correct
34 Correct 116 ms 33016 KB Output is correct
35 Correct 192 ms 37624 KB Output is correct
36 Correct 201 ms 37752 KB Output is correct
37 Correct 121 ms 33272 KB Output is correct
38 Correct 199 ms 36728 KB Output is correct
39 Correct 48 ms 29816 KB Output is correct
40 Correct 192 ms 36728 KB Output is correct
41 Correct 159 ms 34552 KB Output is correct
42 Correct 194 ms 36728 KB Output is correct
43 Correct 78 ms 31352 KB Output is correct
44 Correct 213 ms 36724 KB Output is correct
45 Correct 54 ms 30072 KB Output is correct
46 Correct 198 ms 36856 KB Output is correct
47 Correct 67 ms 30716 KB Output is correct
48 Correct 202 ms 36728 KB Output is correct
49 Correct 392 ms 38244 KB Output is correct
50 Correct 436 ms 38884 KB Output is correct
51 Correct 277 ms 37092 KB Output is correct
52 Correct 429 ms 38884 KB Output is correct
53 Correct 174 ms 33516 KB Output is correct
54 Correct 439 ms 38884 KB Output is correct
55 Correct 368 ms 38116 KB Output is correct
56 Correct 439 ms 38884 KB Output is correct
57 Correct 65 ms 30576 KB Output is correct
58 Correct 441 ms 38884 KB Output is correct
59 Correct 264 ms 36580 KB Output is correct
60 Correct 431 ms 38884 KB Output is correct
61 Correct 272 ms 37988 KB Output is correct
62 Correct 257 ms 37680 KB Output is correct
63 Correct 251 ms 37700 KB Output is correct
64 Correct 222 ms 38248 KB Output is correct
65 Correct 286 ms 38172 KB Output is correct
66 Correct 258 ms 38076 KB Output is correct
67 Correct 265 ms 37636 KB Output is correct
68 Correct 255 ms 37628 KB Output is correct
69 Correct 248 ms 37084 KB Output is correct
70 Correct 265 ms 37472 KB Output is correct
71 Correct 272 ms 37864 KB Output is correct
72 Correct 235 ms 37820 KB Output is correct
73 Correct 692 ms 50400 KB Output is correct
74 Correct 457 ms 44260 KB Output is correct
75 Correct 674 ms 49772 KB Output is correct
76 Correct 847 ms 54620 KB Output is correct
77 Correct 461 ms 43108 KB Output is correct
78 Correct 695 ms 51036 KB Output is correct
79 Correct 755 ms 52572 KB Output is correct
80 Correct 835 ms 54748 KB Output is correct
81 Correct 309 ms 40556 KB Output is correct
82 Correct 654 ms 49116 KB Output is correct
83 Correct 589 ms 48604 KB Output is correct
84 Correct 836 ms 54620 KB Output is correct
85 Correct 526 ms 47800 KB Output is correct
86 Correct 682 ms 51728 KB Output is correct
87 Correct 319 ms 43588 KB Output is correct
88 Correct 614 ms 52072 KB Output is correct
89 Correct 580 ms 49316 KB Output is correct
90 Correct 638 ms 52028 KB Output is correct
91 Correct 400 ms 45444 KB Output is correct
92 Correct 652 ms 51456 KB Output is correct
93 Correct 336 ms 43472 KB Output is correct
94 Correct 650 ms 51804 KB Output is correct
95 Correct 390 ms 44648 KB Output is correct
96 Correct 623 ms 51644 KB Output is correct