oj.uz

Submission #951606

# Submission time Handle Problem Language Result Execution time Memory
951606 2024-03-22T07:26:09 Z hengliao Two Antennas (JOI19_antennas) C++14
24 / 100
 3000 ms 31000 KB 
#include<bits/stdc++.h>
using namespace std;

#define F first
#define S second
#define pb push_back
#define vll vector<ll>
#define pll pair<ll, ll>
typedef long long ll;

const ll mxN=2e5+5;
const ll inf=1e18;

ll h[mxN];
ll a[mxN];
ll b[mxN];
ll n, q;
vll add[mxN];
vll minu[mxN];

struct segtree{
    vll tree;
    ll treelen;

    void init(ll siz){
        treelen=siz+1;
        while(__builtin_popcountll(treelen)!=1){
            treelen++;
        }
        tree=vll(2*treelen, 0);
    }

    void update(ll idx, ll val){
        ll tar=treelen+idx;
        tree[tar]=val;
        tar/=2;
        while(tar>0){
            tree[tar]=max(tree[2*tar], tree[2*tar+1]);
            tar/=2;
        }
    }

    ll getmax(ll idx, ll low, ll high, ll qlow, ll qhigh){
        if(low>=qlow && high<=qhigh){
            return tree[idx];
        }
        if(low>qhigh || high<qlow){
            return 0;
        }
        ll mid=(low+high)/2;
        return max(getmax(2*idx, low, mid, qlow, qhigh), 
            getmax(2*idx+1, mid+1, high, qlow, qhigh));
    }
};

struct segtree2{
    vll tree;
    ll treelen;

    void init(ll siz){
        treelen=siz+1;
        while(__builtin_popcountll(treelen)!=1){
            treelen++;
        }
        tree=vll(2*treelen, inf);
    }

    void update(ll idx, ll val){
        ll tar=treelen+idx;
        tree[tar]=val;
        tar/=2;
        while(tar>0){
            tree[tar]=min(tree[2*tar], tree[2*tar+1]);
            tar/=2;
        }
    }

    ll getmin(ll idx, ll low, ll high, ll qlow, ll qhigh){
        if(low>=qlow && high<=qhigh){
            return tree[idx];
        }
        if(low>qhigh || high<qlow){
            return inf;
        }
        ll mid=(low+high)/2;
        return min(getmin(2*idx, low, mid, qlow, qhigh), 
            getmin(2*idx+1, mid+1, high, qlow, qhigh));
    }
};

segtree seg1;
segtree2 seg2;

ll solve2(ll l, ll r){
    seg1.init(n);
    seg2.init(n);
    /*for(auto it:seg2.tree){
        cout<<it<<' ';
    }
    cout<<'\n';*/
    for(ll i=l;i<=r;i++){
        add[i].clear();
        minu[i].clear();
    }
    ll re=-1;
    for(ll i=l;i<=r;i++){
        for(auto it:add[i]){
            seg1.update(it, h[it]);
            seg2.update(it, h[it]);
        }
        
        for(auto it:minu[i]){
            seg1.update(it, 0);
            seg2.update(it, inf);
        }
        if(i+a[i]<=r){
            add[i+a[i]].pb(i);
        }
        if(i+b[i]+1<=r){
            minu[i+b[i]+1].pb(i);
        }
        ll low=i-b[i], high=i-a[i];
        low=max(low, l);
        //cout<<i<<' '<<low<<' '<<high<<'\n';
        if(high<low) continue;
        ll mn=seg2.getmin(1, 0, seg2.treelen-1, low, high);
        //cout<<mn<<'\n';
        if(mn!=inf){
            re=max(re, abs(h[i]-mn));
        }
        ll mx=seg1.getmax(1, 0, seg1.treelen-1, low, high);
        //cout<<mx<<'\n';
        if(mx!=0){
            re=max(re, abs(h[i]-mx));
        }
    }
    return re;
}

void solve(){
    cin>>n;
    for(ll i=0;i<n;i++){
        cin>>h[i]>>a[i]>>b[i];
    }
    cin>>q;
    for(ll i=0;i<q;i++){
        ll l, r;
        cin>>l>>r;
        l--; r--;
        cout<<solve2(l, r);
        if(i<q-1) cout<<'\n';
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    solve();
    return 0;
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12888 KB Output is correct
2 Correct 6 ms 12888 KB Output is correct
3 Correct 4 ms 12976 KB Output is correct
4 Correct 5 ms 12892 KB Output is correct
5 Correct 4 ms 12892 KB Output is correct
6 Correct 4 ms 12892 KB Output is correct
7 Correct 5 ms 13004 KB Output is correct
8 Correct 6 ms 12888 KB Output is correct
9 Correct 4 ms 12948 KB Output is correct
10 Correct 6 ms 12896 KB Output is correct
11 Correct 4 ms 12900 KB Output is correct
12 Correct 6 ms 13000 KB Output is correct
13 Correct 4 ms 12900 KB Output is correct
14 Correct 4 ms 12888 KB Output is correct
15 Correct 3 ms 12892 KB Output is correct
16 Correct 3 ms 13144 KB Output is correct
17 Correct 3 ms 12896 KB Output is correct
18 Correct 4 ms 12896 KB Output is correct
19 Correct 3 ms 12888 KB Output is correct
20 Correct 3 ms 12888 KB Output is correct
21 Correct 5 ms 12980 KB Output is correct
22 Correct 3 ms 12892 KB Output is correct
23 Correct 4 ms 12984 KB Output is correct
24 Correct 4 ms 12892 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12888 KB Output is correct
2 Correct 6 ms 12888 KB Output is correct
3 Correct 4 ms 12976 KB Output is correct
4 Correct 5 ms 12892 KB Output is correct
5 Correct 4 ms 12892 KB Output is correct
6 Correct 4 ms 12892 KB Output is correct
7 Correct 5 ms 13004 KB Output is correct
8 Correct 6 ms 12888 KB Output is correct
9 Correct 4 ms 12948 KB Output is correct
10 Correct 6 ms 12896 KB Output is correct
11 Correct 4 ms 12900 KB Output is correct
12 Correct 6 ms 13000 KB Output is correct
13 Correct 4 ms 12900 KB Output is correct
14 Correct 4 ms 12888 KB Output is correct
15 Correct 3 ms 12892 KB Output is correct
16 Correct 3 ms 13144 KB Output is correct
17 Correct 3 ms 12896 KB Output is correct
18 Correct 4 ms 12896 KB Output is correct
19 Correct 3 ms 12888 KB Output is correct
20 Correct 3 ms 12888 KB Output is correct
21 Correct 5 ms 12980 KB Output is correct
22 Correct 3 ms 12892 KB Output is correct
23 Correct 4 ms 12984 KB Output is correct
24 Correct 4 ms 12892 KB Output is correct
25 Correct 2732 ms 15368 KB Output is correct
26 Correct 605 ms 13216 KB Output is correct
27 Execution timed out 3077 ms 14636 KB Time limit exceeded
28 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 25820 KB Output is correct
2 Correct 148 ms 26196 KB Output is correct
3 Correct 93 ms 24656 KB Output is correct
4 Correct 137 ms 26400 KB Output is correct
5 Correct 55 ms 19292 KB Output is correct
6 Correct 150 ms 26184 KB Output is correct
7 Correct 110 ms 25520 KB Output is correct
8 Correct 178 ms 31000 KB Output is correct
9 Correct 19 ms 15452 KB Output is correct
10 Correct 150 ms 30800 KB Output is correct
11 Correct 80 ms 23068 KB Output is correct
12 Correct 184 ms 30808 KB Output is correct
13 Correct 90 ms 28980 KB Output is correct
14 Correct 87 ms 28880 KB Output is correct
15 Correct 83 ms 29140 KB Output is correct
16 Correct 86 ms 29600 KB Output is correct
17 Correct 91 ms 29324 KB Output is correct
18 Correct 91 ms 29692 KB Output is correct
19 Correct 87 ms 29044 KB Output is correct
20 Correct 89 ms 29100 KB Output is correct
21 Correct 105 ms 28600 KB Output is correct
22 Correct 87 ms 28976 KB Output is correct
23 Correct 97 ms 29032 KB Output is correct
24 Correct 99 ms 28960 KB Output is correct

Subtask #4
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12888 KB Output is correct
2 Correct 6 ms 12888 KB Output is correct
3 Correct 4 ms 12976 KB Output is correct
4 Correct 5 ms 12892 KB Output is correct
5 Correct 4 ms 12892 KB Output is correct
6 Correct 4 ms 12892 KB Output is correct
7 Correct 5 ms 13004 KB Output is correct
8 Correct 6 ms 12888 KB Output is correct
9 Correct 4 ms 12948 KB Output is correct
10 Correct 6 ms 12896 KB Output is correct
11 Correct 4 ms 12900 KB Output is correct
12 Correct 6 ms 13000 KB Output is correct
13 Correct 4 ms 12900 KB Output is correct
14 Correct 4 ms 12888 KB Output is correct
15 Correct 3 ms 12892 KB Output is correct
16 Correct 3 ms 13144 KB Output is correct
17 Correct 3 ms 12896 KB Output is correct
18 Correct 4 ms 12896 KB Output is correct
19 Correct 3 ms 12888 KB Output is correct
20 Correct 3 ms 12888 KB Output is correct
21 Correct 5 ms 12980 KB Output is correct
22 Correct 3 ms 12892 KB Output is correct
23 Correct 4 ms 12984 KB Output is correct
24 Correct 4 ms 12892 KB Output is correct
25 Correct 2732 ms 15368 KB Output is correct
26 Correct 605 ms 13216 KB Output is correct
27 Execution timed out 3077 ms 14636 KB Time limit exceeded
28 Halted 0 ms 0 KB -