oj.uz

Submission #676006

# Submission time Handle Problem Language Result Execution time Memory
676006 2022-12-28T20:48:35 Z urosk Two Antennas (JOI19_antennas) C++14
13 / 100
 150 ms 61724 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[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 9 ms 14428 KB Output is correct
2 Correct 8 ms 14436 KB Output is correct
3 Correct 8 ms 14548 KB Output is correct
4 Correct 8 ms 14568 KB Output is correct
5 Correct 8 ms 14440 KB Output is correct
6 Correct 9 ms 14432 KB Output is correct
7 Correct 9 ms 14508 KB Output is correct
8 Correct 8 ms 14548 KB Output is correct
9 Correct 8 ms 14436 KB Output is correct
10 Correct 9 ms 14564 KB Output is correct
11 Correct 8 ms 14420 KB Output is correct
12 Correct 9 ms 14444 KB Output is correct
13 Correct 10 ms 14420 KB Output is correct
14 Correct 8 ms 14548 KB Output is correct
15 Correct 8 ms 14436 KB Output is correct
16 Correct 8 ms 14440 KB Output is correct
17 Correct 8 ms 14548 KB Output is correct
18 Correct 8 ms 14436 KB Output is correct
19 Correct 8 ms 14416 KB Output is correct
20 Correct 8 ms 14548 KB Output is correct
21 Correct 9 ms 14472 KB Output is correct
22 Correct 8 ms 14432 KB Output is correct
23 Correct 10 ms 14548 KB Output is correct
24 Correct 8 ms 14432 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14428 KB Output is correct
2 Correct 8 ms 14436 KB Output is correct
3 Correct 8 ms 14548 KB Output is correct
4 Correct 8 ms 14568 KB Output is correct
5 Correct 8 ms 14440 KB Output is correct
6 Correct 9 ms 14432 KB Output is correct
7 Correct 9 ms 14508 KB Output is correct
8 Correct 8 ms 14548 KB Output is correct
9 Correct 8 ms 14436 KB Output is correct
10 Correct 9 ms 14564 KB Output is correct
11 Correct 8 ms 14420 KB Output is correct
12 Correct 9 ms 14444 KB Output is correct
13 Correct 10 ms 14420 KB Output is correct
14 Correct 8 ms 14548 KB Output is correct
15 Correct 8 ms 14436 KB Output is correct
16 Correct 8 ms 14440 KB Output is correct
17 Correct 8 ms 14548 KB Output is correct
18 Correct 8 ms 14436 KB Output is correct
19 Correct 8 ms 14416 KB Output is correct
20 Correct 8 ms 14548 KB Output is correct
21 Correct 9 ms 14472 KB Output is correct
22 Correct 8 ms 14432 KB Output is correct
23 Correct 10 ms 14548 KB Output is correct
24 Correct 8 ms 14432 KB Output is correct
25 Correct 104 ms 24012 KB Output is correct
26 Correct 19 ms 15728 KB Output is correct
27 Correct 124 ms 27680 KB Output is correct
28 Correct 130 ms 27888 KB Output is correct
29 Correct 89 ms 24016 KB Output is correct
30 Correct 91 ms 23464 KB Output is correct
31 Correct 93 ms 26424 KB Output is correct
32 Correct 125 ms 27796 KB Output is correct
33 Correct 113 ms 26972 KB Output is correct
34 Correct 67 ms 21108 KB Output is correct
35 Correct 150 ms 27540 KB Output is correct
36 Correct 132 ms 27852 KB Output is correct
37 Correct 73 ms 21672 KB Output is correct
38 Correct 148 ms 26908 KB Output is correct
39 Correct 26 ms 16352 KB Output is correct
40 Correct 114 ms 26808 KB Output is correct
41 Correct 93 ms 23520 KB Output is correct
42 Correct 121 ms 26912 KB Output is correct
43 Correct 47 ms 18712 KB Output is correct
44 Correct 122 ms 26912 KB Output is correct
45 Correct 29 ms 16824 KB Output is correct
46 Correct 116 ms 26964 KB Output is correct
47 Correct 44 ms 17836 KB Output is correct
48 Correct 120 ms 26856 KB Output is correct

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 84 ms 61724 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14428 KB Output is correct
2 Correct 8 ms 14436 KB Output is correct
3 Correct 8 ms 14548 KB Output is correct
4 Correct 8 ms 14568 KB Output is correct
5 Correct 8 ms 14440 KB Output is correct
6 Correct 9 ms 14432 KB Output is correct
7 Correct 9 ms 14508 KB Output is correct
8 Correct 8 ms 14548 KB Output is correct
9 Correct 8 ms 14436 KB Output is correct
10 Correct 9 ms 14564 KB Output is correct
11 Correct 8 ms 14420 KB Output is correct
12 Correct 9 ms 14444 KB Output is correct
13 Correct 10 ms 14420 KB Output is correct
14 Correct 8 ms 14548 KB Output is correct
15 Correct 8 ms 14436 KB Output is correct
16 Correct 8 ms 14440 KB Output is correct
17 Correct 8 ms 14548 KB Output is correct
18 Correct 8 ms 14436 KB Output is correct
19 Correct 8 ms 14416 KB Output is correct
20 Correct 8 ms 14548 KB Output is correct
21 Correct 9 ms 14472 KB Output is correct
22 Correct 8 ms 14432 KB Output is correct
23 Correct 10 ms 14548 KB Output is correct
24 Correct 8 ms 14432 KB Output is correct
25 Correct 104 ms 24012 KB Output is correct
26 Correct 19 ms 15728 KB Output is correct
27 Correct 124 ms 27680 KB Output is correct
28 Correct 130 ms 27888 KB Output is correct
29 Correct 89 ms 24016 KB Output is correct
30 Correct 91 ms 23464 KB Output is correct
31 Correct 93 ms 26424 KB Output is correct
32 Correct 125 ms 27796 KB Output is correct
33 Correct 113 ms 26972 KB Output is correct
34 Correct 67 ms 21108 KB Output is correct
35 Correct 150 ms 27540 KB Output is correct
36 Correct 132 ms 27852 KB Output is correct
37 Correct 73 ms 21672 KB Output is correct
38 Correct 148 ms 26908 KB Output is correct
39 Correct 26 ms 16352 KB Output is correct
40 Correct 114 ms 26808 KB Output is correct
41 Correct 93 ms 23520 KB Output is correct
42 Correct 121 ms 26912 KB Output is correct
43 Correct 47 ms 18712 KB Output is correct
44 Correct 122 ms 26912 KB Output is correct
45 Correct 29 ms 16824 KB Output is correct
46 Correct 116 ms 26964 KB Output is correct
47 Correct 44 ms 17836 KB Output is correct
48 Correct 120 ms 26856 KB Output is correct
49 Runtime error 84 ms 61724 KB Execution killed with signal 11
50 Halted 0 ms 0 KB -