Submission #861319

#	Time	Username	Problem	Language	Result	Execution time	Memory
861319		guagua0407	Two Antennas (JOI19_antennas)	C++17	100 / 100	499 ms	44660 KiB

antennas

//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

void setIO(string s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}

struct node{
    int d,c;
};

const int mxn=2e5+5;
node segtree[mxn*4];
int lazy[mxn*4];
int n,q;
int h[mxn];
int a[mxn],b[mxn];
vector<int> st[mxn],en[mxn],enq[mxn];
int L[mxn],R[mxn];
int ans[mxn];
int inf=1e9+1;

void push(int v){
    lazy[v*2]=min(lazy[v*2],lazy[v]);
    lazy[v*2+1]=min(lazy[v*2+1],lazy[v]);
    segtree[v*2].d=max(segtree[v*2].d,segtree[v*2].c-lazy[v]);
    segtree[v*2+1].d=max(segtree[v*2+1].d,segtree[v*2+1].c-lazy[v]);
    lazy[v]=inf;
}

void pull(int v){
    segtree[v].c=max(segtree[v*2].c,segtree[v*2+1].c);
    segtree[v].d=max(segtree[v*2].d,segtree[v*2+1].d);
}

void update(int pos,int l=1,int r=n,int v=1){
    if(l==r){
        segtree[v].c=h[pos];
        return;
    }
    push(v);
    int mid=(l+r)/2;
    if(pos<=mid) update(pos,l,mid,v*2);
    else update(pos,mid+1,r,v*2+1);
    pull(v);
}

void erase(int pos,int l=1,int r=n,int v=1){
    if(l==r){
        segtree[v].c=-inf;
        return;
    }
    push(v);
    int mid=(l+r)/2;
    if(pos<=mid) erase(pos,l,mid,v*2);
    else erase(pos,mid+1,r,v*2+1);
    pull(v);
}

void update2(int tl,int tr,int val,int l=1,int r=n,int v=1){
    if(r<tl or tr<l){
        return;
    }
    if(tl<=l and r<=tr){
        segtree[v].d=max(segtree[v].d,segtree[v].c-val);
        lazy[v]=min(lazy[v],val);
        return;
    }
    push(v);
    int mid=(l+r)/2;
    update2(tl,min(mid,tr),val,l,mid,v*2);
    update2(max(mid+1,tl),tr,val,mid+1,r,v*2+1);
    pull(v);
}

int query(int tl,int tr,int l=1,int r=n,int v=1){
    if(r<tl or tr<l){
        return -1;
    }
    if(tl<=l and r<=tr){
        return segtree[v].d;
    }
    push(v);
    int mid=(l+r)/2;
    return max(query(tl,min(mid,tr),l,mid,v*2),query(max(mid+1,tl),tr,mid+1,r,v*2+1));
}

void solve(){
    for(int i=0;i<mxn*4;i++){
        segtree[i].c=-inf;
        lazy[i]=inf;
        segtree[i].d=-1;
    }
    for(int i=1;i<=n;i++){
        for(auto v:st[i]){
            update(v);
        }
        for(auto v:en[i]){
            erase(v);
        }
        int l=i-b[i];
        int r=i-a[i];
        if(r>=1){
            l=max(l,1);
            update2(l,r,h[i]);
        }
        for(auto v:enq[i]){
            ans[v]=max(ans[v],query(L[v],R[v]));
        }
    }
}

int main() {_
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>h[i]>>a[i]>>b[i];
    }
    cin>>q;
    for(int i=0;i<q;i++){
        int l,r;
        cin>>l>>r;
        L[i]=l,R[i]=r;
        enq[r].push_back(i);
        ans[i]=-1;
    }
    for(int i=1;i<=n;i++){
        int l=i+a[i];
        int r=i+b[i];
        if(l>n) continue;
        r=min(r,n);
        st[l].push_back(i);
        en[r+1].push_back(i);
    }
    solve();
    for(int i=1;i<=n;i++){
        h[i]=inf-h[i];
    }
    solve();
    for(int i=0;i<q;i++){
        cout<<max(-1,ans[i])<<'\n';
    }
    return 0;
}
//maybe its multiset not set

Compilation message (stderr)

antennas.cpp: In function 'void setIO(std::string)':
antennas.cpp:12:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |     freopen((s + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:13:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |     freopen((s + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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