oj.uz

답안 #676009

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
676009 2022-12-28T20:52:20 Z urosk Two Antennas (JOI19_antennas) C++14
100 / 100
 906 ms 55184 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 200005
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[4*maxn],rs[4*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

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 9 ms 14508 KB Output is correct
3 Correct 8 ms 14432 KB Output is correct
4 Correct 8 ms 14548 KB Output is correct
5 Correct 9 ms 14548 KB Output is correct
6 Correct 8 ms 14548 KB Output is correct
7 Correct 8 ms 14560 KB Output is correct
8 Correct 8 ms 14548 KB Output is correct
9 Correct 9 ms 14420 KB Output is correct
10 Correct 9 ms 14560 KB Output is correct
11 Correct 8 ms 14420 KB Output is correct
12 Correct 8 ms 14548 KB Output is correct
13 Correct 8 ms 14428 KB Output is correct
14 Correct 8 ms 14432 KB Output is correct
15 Correct 8 ms 14428 KB Output is correct
16 Correct 10 ms 14424 KB Output is correct
17 Correct 9 ms 14432 KB Output is correct
18 Correct 8 ms 14472 KB Output is correct
19 Correct 8 ms 14420 KB Output is correct
20 Correct 9 ms 14428 KB Output is correct
21 Correct 8 ms 14432 KB Output is correct
22 Correct 8 ms 14420 KB Output is correct
23 Correct 8 ms 14420 KB Output is correct
24 Correct 9 ms 14428 KB Output is correct

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 9 ms 14508 KB Output is correct
3 Correct 8 ms 14432 KB Output is correct
4 Correct 8 ms 14548 KB Output is correct
5 Correct 9 ms 14548 KB Output is correct
6 Correct 8 ms 14548 KB Output is correct
7 Correct 8 ms 14560 KB Output is correct
8 Correct 8 ms 14548 KB Output is correct
9 Correct 9 ms 14420 KB Output is correct
10 Correct 9 ms 14560 KB Output is correct
11 Correct 8 ms 14420 KB Output is correct
12 Correct 8 ms 14548 KB Output is correct
13 Correct 8 ms 14428 KB Output is correct
14 Correct 8 ms 14432 KB Output is correct
15 Correct 8 ms 14428 KB Output is correct
16 Correct 10 ms 14424 KB Output is correct
17 Correct 9 ms 14432 KB Output is correct
18 Correct 8 ms 14472 KB Output is correct
19 Correct 8 ms 14420 KB Output is correct
20 Correct 9 ms 14428 KB Output is correct
21 Correct 8 ms 14432 KB Output is correct
22 Correct 8 ms 14420 KB Output is correct
23 Correct 8 ms 14420 KB Output is correct
24 Correct 9 ms 14428 KB Output is correct
25 Correct 89 ms 22928 KB Output is correct
26 Correct 19 ms 15700 KB Output is correct
27 Correct 128 ms 26008 KB Output is correct
28 Correct 134 ms 26204 KB Output is correct
29 Correct 90 ms 22964 KB Output is correct
30 Correct 84 ms 22412 KB Output is correct
31 Correct 92 ms 25016 KB Output is correct
32 Correct 125 ms 26112 KB Output is correct
33 Correct 111 ms 25472 KB Output is correct
34 Correct 64 ms 20200 KB Output is correct
35 Correct 117 ms 25972 KB Output is correct
36 Correct 121 ms 26196 KB Output is correct
37 Correct 71 ms 20828 KB Output is correct
38 Correct 117 ms 25064 KB Output is correct
39 Correct 26 ms 16288 KB Output is correct
40 Correct 118 ms 25104 KB Output is correct
41 Correct 87 ms 22316 KB Output is correct
42 Correct 118 ms 25168 KB Output is correct
43 Correct 44 ms 18252 KB Output is correct
44 Correct 115 ms 25288 KB Output is correct
45 Correct 28 ms 16516 KB Output is correct
46 Correct 123 ms 25264 KB Output is correct
47 Correct 36 ms 17512 KB Output is correct
48 Correct 116 ms 25156 KB Output is correct

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 433 ms 42260 KB Output is correct
2 Correct 502 ms 44688 KB Output is correct
3 Correct 312 ms 35424 KB Output is correct
4 Correct 523 ms 44528 KB Output is correct
5 Correct 202 ms 28784 KB Output is correct
6 Correct 511 ms 44484 KB Output is correct
7 Correct 422 ms 39452 KB Output is correct
8 Correct 502 ms 44600 KB Output is correct
9 Correct 47 ms 19280 KB Output is correct
10 Correct 500 ms 44616 KB Output is correct
11 Correct 265 ms 32532 KB Output is correct
12 Correct 495 ms 44472 KB Output is correct
13 Correct 197 ms 40548 KB Output is correct
14 Correct 191 ms 40672 KB Output is correct
15 Correct 187 ms 40472 KB Output is correct
16 Correct 159 ms 41004 KB Output is correct
17 Correct 196 ms 40592 KB Output is correct
18 Correct 178 ms 41072 KB Output is correct
19 Correct 191 ms 40408 KB Output is correct
20 Correct 177 ms 41040 KB Output is correct
21 Correct 188 ms 41732 KB Output is correct
22 Correct 192 ms 41276 KB Output is correct
23 Correct 193 ms 40600 KB Output is correct
24 Correct 157 ms 41036 KB Output is correct

Subtask #4
65.0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 9 ms 14508 KB Output is correct
3 Correct 8 ms 14432 KB Output is correct
4 Correct 8 ms 14548 KB Output is correct
5 Correct 9 ms 14548 KB Output is correct
6 Correct 8 ms 14548 KB Output is correct
7 Correct 8 ms 14560 KB Output is correct
8 Correct 8 ms 14548 KB Output is correct
9 Correct 9 ms 14420 KB Output is correct
10 Correct 9 ms 14560 KB Output is correct
11 Correct 8 ms 14420 KB Output is correct
12 Correct 8 ms 14548 KB Output is correct
13 Correct 8 ms 14428 KB Output is correct
14 Correct 8 ms 14432 KB Output is correct
15 Correct 8 ms 14428 KB Output is correct
16 Correct 10 ms 14424 KB Output is correct
17 Correct 9 ms 14432 KB Output is correct
18 Correct 8 ms 14472 KB Output is correct
19 Correct 8 ms 14420 KB Output is correct
20 Correct 9 ms 14428 KB Output is correct
21 Correct 8 ms 14432 KB Output is correct
22 Correct 8 ms 14420 KB Output is correct
23 Correct 8 ms 14420 KB Output is correct
24 Correct 9 ms 14428 KB Output is correct
25 Correct 89 ms 22928 KB Output is correct
26 Correct 19 ms 15700 KB Output is correct
27 Correct 128 ms 26008 KB Output is correct
28 Correct 134 ms 26204 KB Output is correct
29 Correct 90 ms 22964 KB Output is correct
30 Correct 84 ms 22412 KB Output is correct
31 Correct 92 ms 25016 KB Output is correct
32 Correct 125 ms 26112 KB Output is correct
33 Correct 111 ms 25472 KB Output is correct
34 Correct 64 ms 20200 KB Output is correct
35 Correct 117 ms 25972 KB Output is correct
36 Correct 121 ms 26196 KB Output is correct
37 Correct 71 ms 20828 KB Output is correct
38 Correct 117 ms 25064 KB Output is correct
39 Correct 26 ms 16288 KB Output is correct
40 Correct 118 ms 25104 KB Output is correct
41 Correct 87 ms 22316 KB Output is correct
42 Correct 118 ms 25168 KB Output is correct
43 Correct 44 ms 18252 KB Output is correct
44 Correct 115 ms 25288 KB Output is correct
45 Correct 28 ms 16516 KB Output is correct
46 Correct 123 ms 25264 KB Output is correct
47 Correct 36 ms 17512 KB Output is correct
48 Correct 116 ms 25156 KB Output is correct
49 Correct 433 ms 42260 KB Output is correct
50 Correct 502 ms 44688 KB Output is correct
51 Correct 312 ms 35424 KB Output is correct
52 Correct 523 ms 44528 KB Output is correct
53 Correct 202 ms 28784 KB Output is correct
54 Correct 511 ms 44484 KB Output is correct
55 Correct 422 ms 39452 KB Output is correct
56 Correct 502 ms 44600 KB Output is correct
57 Correct 47 ms 19280 KB Output is correct
58 Correct 500 ms 44616 KB Output is correct
59 Correct 265 ms 32532 KB Output is correct
60 Correct 495 ms 44472 KB Output is correct
61 Correct 197 ms 40548 KB Output is correct
62 Correct 191 ms 40672 KB Output is correct
63 Correct 187 ms 40472 KB Output is correct
64 Correct 159 ms 41004 KB Output is correct
65 Correct 196 ms 40592 KB Output is correct
66 Correct 178 ms 41072 KB Output is correct
67 Correct 191 ms 40408 KB Output is correct
68 Correct 177 ms 41040 KB Output is correct
69 Correct 188 ms 41732 KB Output is correct
70 Correct 192 ms 41276 KB Output is correct
71 Correct 193 ms 40600 KB Output is correct
72 Correct 157 ms 41036 KB Output is correct
73 Correct 710 ms 49712 KB Output is correct
74 Correct 528 ms 45388 KB Output is correct
75 Correct 614 ms 46000 KB Output is correct
76 Correct 906 ms 55184 KB Output is correct
77 Correct 383 ms 36404 KB Output is correct
78 Correct 738 ms 51384 KB Output is correct
79 Correct 763 ms 50892 KB Output is correct
80 Correct 862 ms 54956 KB Output is correct
81 Correct 237 ms 30276 KB Output is correct
82 Correct 680 ms 49416 KB Output is correct
83 Correct 544 ms 43956 KB Output is correct
84 Correct 897 ms 54972 KB Output is correct
85 Correct 386 ms 46700 KB Output is correct
86 Correct 491 ms 51172 KB Output is correct
87 Correct 243 ms 42040 KB Output is correct
88 Correct 483 ms 51216 KB Output is correct
89 Correct 423 ms 48044 KB Output is correct
90 Correct 508 ms 51012 KB Output is correct
91 Correct 292 ms 43776 KB Output is correct
92 Correct 484 ms 51488 KB Output is correct
93 Correct 246 ms 43532 KB Output is correct
94 Correct 509 ms 51660 KB Output is correct
95 Correct 275 ms 43220 KB Output is correct
96 Correct 479 ms 51648 KB Output is correct