Submission #1170139

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170139		Piokemon	Two Antennas (JOI19_antennas)	C++20	22 / 100	111 ms	25852 KiB

antennas

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;

constexpr int N = 2e5;
constexpr int base = (1<<18);
pair<ll,ll> tree[2*base+9];

pair<ll,ll> merg(pair<ll,ll> a, pair<ll,ll> b){
    return {max(a.first,b.first),min(a.second,b.second)};
}

void sed(int x, int val){
    x+=base; tree[x]={val,val};
    if (val==-1)tree[x]={-2e9,2e9};
    x/=2;
    while(x){
        tree[x] = merg(tree[2*x],tree[2*x+1]);
        x/=2;
    }
}

pair<ll,ll> query(int x, int a,  int b, int p, int k){
    if (a>k || b<p)return {-2e9,2e9};
    if (p<=a && b<=k)return tree[x];
    int mid=(a+b)/2;
    return merg(query(2*x,a,mid,p,k),query(2*x+1,mid+1,b,p,k));
}

vector<pair<int,int>> akt[2*N+9];

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n,h,a,b;
    cin >> n;
    for (int x=0;x<=2*base;x++)tree[x]={-2e9,2e9};
    ll odp=-1;
    for (int x=1;x<=n;x++){
        for (pair<int,int> y:akt[x]){
            sed(y.first,y.second);
        }
        cin >> h >> a >> b;
        pair<ll,ll> temp = query(1,0,base-1,max(0,x-b),max(0,x-a));
        odp = max(odp,temp.first-h); odp = max(odp,h-temp.second);
        akt[x+a].push_back({x,h});
        akt[x+b+1].push_back({x,-1});
    }
    int q; cin >> q;
    cin >> q; cin >> q;
    cout << odp << '\n';
}

• Subtask 1: 0 / 2
• Subtask 2: 0 / 11
• Subtask 3: 22 / 22
• Subtask 4: 0 / 65