oj.uz

Submission #583337

# Submission time Handle Problem Language Result Execution time Memory
583337 2022-06-25T08:51:21 Z 79brue Two Antennas (JOI19_antennas) C++17
0 / 100
 361 ms 39064 KB 
#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]);
        ans[i] = max(ans[i*2], ans[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

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

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 9684 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 9684 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 330 ms 37400 KB Output is correct
2 Correct 361 ms 37680 KB Output is correct
3 Correct 273 ms 35456 KB Output is correct
4 Correct 353 ms 39016 KB Output is correct
5 Correct 153 ms 24908 KB Output is correct
6 Correct 334 ms 39064 KB Output is correct
7 Incorrect 316 ms 38112 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 65.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 9684 KB Output isn't correct
2 Halted 0 ms 0 KB -