oj.uz

Submission #879344

# Submission time Handle Problem Language Result Execution time Memory
879344 2023-11-27T07:24:52 Z 12345678 Two Antennas (JOI19_antennas) C++17
22 / 100
 174 ms 35876 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=2e5+5;

ll n, h[nx], a[nx], b[nx], ans=-1;
vector<ll> add[nx], rem[nx];

struct segtree
{
    ll d[4*nx], t=0;
    void build(int l, int r, int i)
    {
        d[i]=t?-2e9:2e9;
        if (l==r) return;
        int md=(l+r)/2;
        build(l, md, 2*i);
        build(md+1, r, 2*i+1);
    }
    void update(int l, int r, int i, int idx, int vl)
    {
        if (r<idx||idx<l) return;
        if (l==r) return void(d[i]=vl);
        int md=(l+r)/2;
        update(l, md, 2*i, idx, vl);
        update(md+1, r, 2*i+1, idx, vl);
        if (t) d[i]=max(d[2*i], d[2*i+1]);
        else d[i]=min(d[2*i], d[2*i+1]);
    }
    ll query(int l, int r, int i, int ql, int qr)
    {
        if (qr<l||r<ql) return t?-2e9:2e9;
        if (ql<=l&&r<=qr) return d[i];
        int md=(l+r)/2;
        if (t) return max(query(l, md, 2*i, ql, qr), query(md+1, r, 2*i+1, ql, qr));
        else return min(query(l, md, 2*i, ql, qr), query(md+1, r, 2*i+1, ql, qr));
    }
} mx, mn;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n;
    mx.t=1;
    mx.build(1, n, 1);
    mn.build(1, n, 1);
    for (int i=1; i<=n; i++) cin>>h[i]>>a[i]>>b[i], add[min(nx-1ll, i+a[i])].push_back(i), rem[min(nx-1ll, i+b[i])].push_back(i);
    for (int i=1; i<=n; i++)
    {
        for (auto x:add[i]) mx.update(1, n, 1, x, h[x]), mn.update(1, n, 1, x, h[x]);
        if (i-a[i]>=1) 
        {
            ans=max({ans, mx.query(1, n, 1, max(1ll, i-b[i]), i-a[i])-h[i], -mn.query(1, n, 1, max(1ll, i-b[i]), i-a[i])+h[i]});
            //cout<<i<<' '<<i-b[i]<<' '<<i-a[i]<<' '<<mx.query(1, n, 1, max(1, i-b[i]), i-a[i])<<' '<<mn.query(1, n, 1, max(1, i-b[i]), i-a[i])<<'\n';
        }
        for (auto x:rem[i]) mx.update(1, n, 1, x, -2e9), mn.update(1, n, 1, x, 2e9);
    }
    cin>>n>>n>>n;
    cout<<ans;
}

Subtask #1
0 / 2.0

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

Subtask #2
0 / 11.0

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

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 30440 KB Output is correct
2 Correct 170 ms 35832 KB Output is correct
3 Correct 117 ms 32712 KB Output is correct
4 Correct 158 ms 35700 KB Output is correct
5 Correct 85 ms 26160 KB Output is correct
6 Correct 155 ms 35780 KB Output is correct
7 Correct 137 ms 34120 KB Output is correct
8 Correct 167 ms 35784 KB Output is correct
9 Correct 25 ms 21336 KB Output is correct
10 Correct 152 ms 35876 KB Output is correct
11 Correct 102 ms 27856 KB Output is correct
12 Correct 174 ms 35684 KB Output is correct
13 Correct 109 ms 33184 KB Output is correct
14 Correct 105 ms 33512 KB Output is correct
15 Correct 102 ms 33316 KB Output is correct
16 Correct 94 ms 33424 KB Output is correct
17 Correct 109 ms 33144 KB Output is correct
18 Correct 106 ms 33404 KB Output is correct
19 Correct 104 ms 33044 KB Output is correct
20 Correct 103 ms 33732 KB Output is correct
21 Correct 106 ms 33792 KB Output is correct
22 Correct 109 ms 33820 KB Output is correct
23 Correct 106 ms 33196 KB Output is correct
24 Correct 93 ms 33632 KB Output is correct

Subtask #4
0 / 65.0

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