Submission #583338

#	Time	Username	Problem	Language	Result	Execution time	Memory
583338		79brue	Two Antennas (JOI19_antennas)	C++17	100 / 100	681 ms	47520 KiB

antennas

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct segTree{
    ll lMin[800002];
    ll rMaxLazy[800002];
    ll ans[800002];

    void init(int i, int l, int r){
        ans[i] = -2e18, lMin[i] = 1e18, rMaxLazy[i] = -1e18;
        if(l==r) return;
        int m = (l+r)>>1;
        init(i*2, l, m);
        init(i*2+1, m+1, r);
    }

    void propagate(int i, int l, int r){
        if(rMaxLazy[i] == -1e18) return;
        ans[i] = max(ans[i], rMaxLazy[i] - lMin[i]);
        if(l!=r){
            rMaxLazy[i*2] = max(rMaxLazy[i*2], rMaxLazy[i]);
            rMaxLazy[i*2+1] = max(rMaxLazy[i*2+1], rMaxLazy[i]);
        }
        rMaxLazy[i] = -1e18;
    }

    void updateL(int i, int l, int r, int x, ll v){
        propagate(i, l, r);
        if(l==r){
            lMin[i] = v;
            return;
        }
        int m = (l+r)>>1;
        if(x<=m) updateL(i*2, l, m, x, v);
        else updateL(i*2+1, m+1, r, x, v);
        lMin[i] = min(lMin[i*2], lMin[i*2+1]);
    }

    void updateR(int i, int l, int r, int s, int e, ll v){
        propagate(i, l, r);
        if(r<s || e<l) return;
        if(s<=l && r<=e){
            rMaxLazy[i] = v;
            propagate(i, l, r);
            return;
        }
        int m = (l+r)>>1;
        updateR(i*2, l, m, s, e, v);
        updateR(i*2+1, m+1, r, s, e, v);
        ans[i] = max(ans[i*2], ans[i*2+1]);
    }

    ll query(int i, int l, int r, int s, int e){
        propagate(i, l, r);
        if(r<s || e<l) return -1;
        if(s<=l && r<=e) return ans[i];
        int m = (l+r)>>1;
        return max(query(i*2, l, m, s, e), query(i*2+1, m+1, r, s, e));
    }
} tree;

int n, q;
ll h[200002];
int a[200002], b[200002];
ll ans[200002];
int l[200002], r[200002];
vector<pair<int, int> > query[200002]; /// (쿼리 번호, l)
vector<pair<int, ll> > update[200002];

void solve(){
    for(int i=1; i<=n; i++){
        query[i].clear();
        update[i].clear();
    }
    for(int i=1; i<=q; i++){
        query[r[i]].push_back(make_pair(i, l[i]));
    }
    for(int i=1; i<=n; i++){
        update[min(i+a[i], n+1)].push_back(make_pair(i, h[i]));
        update[min(i+b[i]+1, n+1)].push_back(make_pair(i, 1e18));
    }

    tree.init(1, 1, n);
    for(int i=1; i<=n; i++){
        for(auto p: update[i]){
            tree.updateL(1, 1, n, p.first, p.second);
        }
        tree.updateR(1, 1, n, i-b[i], i-a[i], h[i]);
        for(auto p: query[i]){
            ans[p.first] = max(ans[p.first], tree.query(1, 1, n, p.second, i));
        }
    }
}

int main(){
    scanf("%d", &n);
    for(int i=1; i<=n; i++){
        scanf("%lld %d %d", &h[i], &a[i], &b[i]);
    }
    scanf("%d", &q);
    for(int i=1; i<=q; i++){
        scanf("%d %d", &l[i], &r[i]);
        ans[i] = -1;
    }

    solve();

    for(int i=1; i<=n; i++) h[i] = 1000000001 - h[i];

    solve();

    for(int i=1; i<=q; i++) printf("%lld\n", ans[i]);
}

Compilation message (stderr)

antennas.cpp: In function 'int main()':
antennas.cpp:99:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
antennas.cpp:101:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |         scanf("%lld %d %d", &h[i], &a[i], &b[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:103:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
antennas.cpp:105:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |         scanf("%d %d", &l[i], &r[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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