oj.uz

Submission #676008

# Submission time Handle Problem Language Result Execution time Memory
676008 2022-12-28T20:51:11 Z urosk Two Antennas (JOI19_antennas) C++14
100 / 100
 859 ms 104344 KB 
#define here cerr<<"===========================================\n"
#define dbg(x) cerr<<#x<<": "<<x<<endl;
#include "bits/stdc++.h"
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
#define ld double
#define ll long long
#define llinf 1000000000000000000LL // 10^17
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define sz(a) (ll)(a.size())
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {cerr<<#a<<": ";for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
#define cer(a) {cerr<<#a<<": ";for(ll x_ : a) cerr<<x_<< " ";cerr<<endl;}

#define daj_mi_malo_vremena ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);

using namespace std;
//using namespace __gnu_pbds;
/*
ll add(ll x,ll y){
    x+=y;
    if(x<0){
        x%=mod;
        x+=mod;
    }else{
        if(x>=mod) x%=mod;
    }
    return x;
}
ll mul(ll a,ll b){
	ll ans = (a*b)%mod;
	if(ans<0) ans+=mod;
	return ans;
}
typedef tree<int,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
typedef tree<int,null_type,less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_multiset;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll rnd(ll l,ll r){
    return uniform_int_distribution<ll>(l,r)(rng);
}
*/
#define maxn 800005
ll n,q;
ll h[maxn],a[maxn],b[maxn];
pll v[maxn];
ll t[4*maxn],t2[4*maxn],lazy[4*maxn];
ll ans[maxn];
vector<pll> kv[maxn];
vector<ll> add[maxn],del[maxn];
ll ls[maxn],rs[maxn],tsz = 0,root = 0;
void init(ll &v,ll tl,ll tr){
    v = ++tsz;
    t[v] = t2[v] = lazy[v] = -llinf;
    if(tl==tr) return;
    ll mid = (tl+tr)/2;
    init(ls[v],tl,mid);
    init(rs[v],mid+1,tr);
}
void upd(ll v,ll x){
    t[v] = max(t[v],t2[v]+x);
    lazy[v] = max(lazy[v],x);
}
void push(ll v){
    if(lazy[v]!=-llinf){
        upd(ls[v],lazy[v]);
        upd(rs[v],lazy[v]);
        lazy[v] = -llinf;
    }
}
void upd2(ll v,ll tl,ll tr,ll i,ll x){
    if(tl==tr){t2[v] = x;return;}
    push(v);
    ll mid = (tl+tr)/2;
    if(i<=mid) upd2(ls[v],tl,mid,i,x);
    else upd2(rs[v],mid+1,tr,i,x);
    t2[v] = max(t2[ls[v]],t2[rs[v]]);
}
void upd(ll v,ll tl,ll tr,ll l,ll r,ll x){
    if(tl>tr||r<tl||l>tr) return;
    if(tl>=l&&tr<=r){upd(v,x);return;}
    push(v);
    ll mid = (tl+tr)/2;
    upd(ls[v],tl,mid,l,r,x);
    upd(rs[v],mid+1,tr,l,r,x);
    t[v] = max(t[ls[v]],t[rs[v]]);
}
ll get(ll v,ll tl,ll tr,ll l,ll r){
    if(l>r) return -llinf;
    if(tl==l&&tr==r) return t[v];
    push(v);
    ll mid = (tl+tr)/2;
    return max(get(ls[v],tl,mid,l,min(mid,r)),get(rs[v],mid+1,tr,max(mid+1,l),r));
}
void reshi(){
    init(root,1,n);
    for(ll i = 1;i<=n;i++){
        ll l = min(n+1,i+a[i]);
        ll r = min(n+1,i+b[i]);
        add[l].pb(i);
        del[r].pb(i);
        for(ll j : add[i]) upd2(root,1,n,j,h[j]);
        upd(root,1,n,i-b[i],i-a[i],-h[i]);
        for(pll p : kv[i]) ans[p.sc] = max(ans[p.sc],get(root,1,n,p.fi,i));
        for(ll j : del[i]) upd2(root,1,n,j,-llinf);
        add[i].clear();
        del[i].clear();
    }
    for(ll i = 0;i<=tsz;i++) rs[i] = ls[i] = 0;
    root = tsz = 0;
}
void tc(){
    cin >> n;
    for(ll i = 1;i<=n;i++) cin >> h[i] >> a[i] >> b[i];
    cin >> q;
    for(ll i = 1;i<=q;i++) cin >> v[i].fi >> v[i].sc;
    for(ll i = 1;i<=q;i++) kv[v[i].sc].pb({v[i].fi,i}),ans[i] = -1;
    reshi();
    for(ll i = 1;i<=n;i++) h[i] = -h[i];
    reshi();
    for(ll i = 1;i<=q;i++) cout<<ans[i]<<endl;
}
int main(){
	daj_mi_malo_vremena
    int t; t = 1;
    while(t--){
        tc();
    }
	return 0;
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 56660 KB Output is correct
2 Correct 29 ms 56788 KB Output is correct
3 Correct 30 ms 56884 KB Output is correct
4 Correct 29 ms 56840 KB Output is correct
5 Correct 27 ms 56788 KB Output is correct
6 Correct 27 ms 56728 KB Output is correct
7 Correct 26 ms 56724 KB Output is correct
8 Correct 28 ms 56760 KB Output is correct
9 Correct 26 ms 56780 KB Output is correct
10 Correct 26 ms 56788 KB Output is correct
11 Correct 27 ms 56660 KB Output is correct
12 Correct 27 ms 56788 KB Output is correct
13 Correct 29 ms 56728 KB Output is correct
14 Correct 30 ms 56812 KB Output is correct
15 Correct 30 ms 56724 KB Output is correct
16 Correct 26 ms 56780 KB Output is correct
17 Correct 27 ms 56724 KB Output is correct
18 Correct 27 ms 56724 KB Output is correct
19 Correct 27 ms 56768 KB Output is correct
20 Correct 27 ms 56788 KB Output is correct
21 Correct 32 ms 56800 KB Output is correct
22 Correct 29 ms 56720 KB Output is correct
23 Correct 26 ms 56788 KB Output is correct
24 Correct 32 ms 56788 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 56660 KB Output is correct
2 Correct 29 ms 56788 KB Output is correct
3 Correct 30 ms 56884 KB Output is correct
4 Correct 29 ms 56840 KB Output is correct
5 Correct 27 ms 56788 KB Output is correct
6 Correct 27 ms 56728 KB Output is correct
7 Correct 26 ms 56724 KB Output is correct
8 Correct 28 ms 56760 KB Output is correct
9 Correct 26 ms 56780 KB Output is correct
10 Correct 26 ms 56788 KB Output is correct
11 Correct 27 ms 56660 KB Output is correct
12 Correct 27 ms 56788 KB Output is correct
13 Correct 29 ms 56728 KB Output is correct
14 Correct 30 ms 56812 KB Output is correct
15 Correct 30 ms 56724 KB Output is correct
16 Correct 26 ms 56780 KB Output is correct
17 Correct 27 ms 56724 KB Output is correct
18 Correct 27 ms 56724 KB Output is correct
19 Correct 27 ms 56768 KB Output is correct
20 Correct 27 ms 56788 KB Output is correct
21 Correct 32 ms 56800 KB Output is correct
22 Correct 29 ms 56720 KB Output is correct
23 Correct 26 ms 56788 KB Output is correct
24 Correct 32 ms 56788 KB Output is correct
25 Correct 104 ms 65316 KB Output is correct
26 Correct 39 ms 57848 KB Output is correct
27 Correct 152 ms 68180 KB Output is correct
28 Correct 153 ms 68432 KB Output is correct
29 Correct 104 ms 65128 KB Output is correct
30 Correct 105 ms 64576 KB Output is correct
31 Correct 112 ms 67248 KB Output is correct
32 Correct 164 ms 68248 KB Output is correct
33 Correct 127 ms 67636 KB Output is correct
34 Correct 84 ms 62320 KB Output is correct
35 Correct 160 ms 68316 KB Output is correct
36 Correct 144 ms 68364 KB Output is correct
37 Correct 91 ms 62908 KB Output is correct
38 Correct 137 ms 67396 KB Output is correct
39 Correct 45 ms 58324 KB Output is correct
40 Correct 165 ms 67308 KB Output is correct
41 Correct 124 ms 64472 KB Output is correct
42 Correct 145 ms 67360 KB Output is correct
43 Correct 64 ms 60364 KB Output is correct
44 Correct 133 ms 67328 KB Output is correct
45 Correct 58 ms 58700 KB Output is correct
46 Correct 144 ms 67272 KB Output is correct
47 Correct 56 ms 59536 KB Output is correct
48 Correct 142 ms 67440 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 429 ms 84252 KB Output is correct
2 Correct 585 ms 91152 KB Output is correct
3 Correct 380 ms 80404 KB Output is correct
4 Correct 531 ms 91236 KB Output is correct
5 Correct 196 ms 72764 KB Output is correct
6 Correct 498 ms 91192 KB Output is correct
7 Correct 412 ms 85116 KB Output is correct
8 Correct 489 ms 91056 KB Output is correct
9 Correct 69 ms 61948 KB Output is correct
10 Correct 495 ms 91156 KB Output is correct
11 Correct 298 ms 77368 KB Output is correct
12 Correct 528 ms 91156 KB Output is correct
13 Correct 221 ms 87040 KB Output is correct
14 Correct 226 ms 87148 KB Output is correct
15 Correct 210 ms 86908 KB Output is correct
16 Correct 195 ms 87552 KB Output is correct
17 Correct 228 ms 87056 KB Output is correct
18 Correct 236 ms 87488 KB Output is correct
19 Correct 240 ms 86936 KB Output is correct
20 Correct 221 ms 87504 KB Output is correct
21 Correct 241 ms 88144 KB Output is correct
22 Correct 240 ms 87748 KB Output is correct
23 Correct 212 ms 87052 KB Output is correct
24 Correct 185 ms 87412 KB Output is correct

Subtask #4
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 56660 KB Output is correct
2 Correct 29 ms 56788 KB Output is correct
3 Correct 30 ms 56884 KB Output is correct
4 Correct 29 ms 56840 KB Output is correct
5 Correct 27 ms 56788 KB Output is correct
6 Correct 27 ms 56728 KB Output is correct
7 Correct 26 ms 56724 KB Output is correct
8 Correct 28 ms 56760 KB Output is correct
9 Correct 26 ms 56780 KB Output is correct
10 Correct 26 ms 56788 KB Output is correct
11 Correct 27 ms 56660 KB Output is correct
12 Correct 27 ms 56788 KB Output is correct
13 Correct 29 ms 56728 KB Output is correct
14 Correct 30 ms 56812 KB Output is correct
15 Correct 30 ms 56724 KB Output is correct
16 Correct 26 ms 56780 KB Output is correct
17 Correct 27 ms 56724 KB Output is correct
18 Correct 27 ms 56724 KB Output is correct
19 Correct 27 ms 56768 KB Output is correct
20 Correct 27 ms 56788 KB Output is correct
21 Correct 32 ms 56800 KB Output is correct
22 Correct 29 ms 56720 KB Output is correct
23 Correct 26 ms 56788 KB Output is correct
24 Correct 32 ms 56788 KB Output is correct
25 Correct 104 ms 65316 KB Output is correct
26 Correct 39 ms 57848 KB Output is correct
27 Correct 152 ms 68180 KB Output is correct
28 Correct 153 ms 68432 KB Output is correct
29 Correct 104 ms 65128 KB Output is correct
30 Correct 105 ms 64576 KB Output is correct
31 Correct 112 ms 67248 KB Output is correct
32 Correct 164 ms 68248 KB Output is correct
33 Correct 127 ms 67636 KB Output is correct
34 Correct 84 ms 62320 KB Output is correct
35 Correct 160 ms 68316 KB Output is correct
36 Correct 144 ms 68364 KB Output is correct
37 Correct 91 ms 62908 KB Output is correct
38 Correct 137 ms 67396 KB Output is correct
39 Correct 45 ms 58324 KB Output is correct
40 Correct 165 ms 67308 KB Output is correct
41 Correct 124 ms 64472 KB Output is correct
42 Correct 145 ms 67360 KB Output is correct
43 Correct 64 ms 60364 KB Output is correct
44 Correct 133 ms 67328 KB Output is correct
45 Correct 58 ms 58700 KB Output is correct
46 Correct 144 ms 67272 KB Output is correct
47 Correct 56 ms 59536 KB Output is correct
48 Correct 142 ms 67440 KB Output is correct
49 Correct 429 ms 84252 KB Output is correct
50 Correct 585 ms 91152 KB Output is correct
51 Correct 380 ms 80404 KB Output is correct
52 Correct 531 ms 91236 KB Output is correct
53 Correct 196 ms 72764 KB Output is correct
54 Correct 498 ms 91192 KB Output is correct
55 Correct 412 ms 85116 KB Output is correct
56 Correct 489 ms 91056 KB Output is correct
57 Correct 69 ms 61948 KB Output is correct
58 Correct 495 ms 91156 KB Output is correct
59 Correct 298 ms 77368 KB Output is correct
60 Correct 528 ms 91156 KB Output is correct
61 Correct 221 ms 87040 KB Output is correct
62 Correct 226 ms 87148 KB Output is correct
63 Correct 210 ms 86908 KB Output is correct
64 Correct 195 ms 87552 KB Output is correct
65 Correct 228 ms 87056 KB Output is correct
66 Correct 236 ms 87488 KB Output is correct
67 Correct 240 ms 86936 KB Output is correct
68 Correct 221 ms 87504 KB Output is correct
69 Correct 241 ms 88144 KB Output is correct
70 Correct 240 ms 87748 KB Output is correct
71 Correct 212 ms 87052 KB Output is correct
72 Correct 185 ms 87412 KB Output is correct
73 Correct 730 ms 97564 KB Output is correct
74 Correct 613 ms 92076 KB Output is correct
75 Correct 695 ms 93756 KB Output is correct
76 Correct 859 ms 104344 KB Output is correct
77 Correct 390 ms 82240 KB Output is correct
78 Correct 723 ms 99448 KB Output is correct
79 Correct 744 ms 99180 KB Output is correct
80 Correct 859 ms 104108 KB Output is correct
81 Correct 247 ms 75076 KB Output is correct
82 Correct 677 ms 97236 KB Output is correct
83 Correct 598 ms 91208 KB Output is correct
84 Correct 856 ms 104108 KB Output is correct
85 Correct 404 ms 94564 KB Output is correct
86 Correct 517 ms 100308 KB Output is correct
87 Correct 273 ms 88884 KB Output is correct
88 Correct 499 ms 100392 KB Output is correct
89 Correct 443 ms 96548 KB Output is correct
90 Correct 527 ms 100236 KB Output is correct
91 Correct 316 ms 91252 KB Output is correct
92 Correct 522 ms 100672 KB Output is correct
93 Correct 266 ms 90468 KB Output is correct
94 Correct 506 ms 100808 KB Output is correct
95 Correct 292 ms 90464 KB Output is correct
96 Correct 507 ms 100688 KB Output is correct