Submission #925248

#	Time	Username	Problem	Language	Result	Execution time	Memory
925248		12345678	Two Antennas (JOI19_antennas)	C++17	100 / 100	450 ms	51028 KiB

antennas

#include <bits/stdc++.h>

using namespace std;

const int nx=2e5+5, inf=1e9+5;

int n, q, h[nx], a[nx], b[nx], res[nx], l[nx], r[nx];
vector<int> qrs[nx], add[nx], rem[nx];

struct segtree
{
    struct node {
        int mx, mn, ans, lzmx, lzmn;
        node(): mx(-inf), mn(inf), lzmx(-inf), lzmn(inf), ans(-1) {}
    } d[4*nx];
    node merge(node &lhs, node &rhs)
    {
        node tmp;
        tmp.mx=max(lhs.mx, rhs.mx);
        tmp.mn=min(lhs.mn, rhs.mn);
        tmp.ans=max(lhs.ans, rhs.ans);
        return tmp;
    }
    void pushlz(int l, int r, int i)
    {
        if (d[i].lzmx==-inf) return;
        d[i].ans=max({d[i].ans, d[i].mx-d[i].lzmn, d[i].lzmx-d[i].mn});
        if (l!=r) d[2*i].lzmx=max(d[2*i].lzmx, d[i].lzmx), d[2*i].lzmn=min(d[2*i].lzmn, d[i].lzmn);
        if (l!=r) d[2*i+1].lzmx=max(d[2*i+1].lzmx, d[i].lzmx), d[2*i+1].lzmn=min(d[2*i+1].lzmn, d[i].lzmn);
        d[i].lzmx=-inf;
        d[i].lzmn=inf;
    }
    void open(int l, int r, int i, int idx, int t)
    {
        pushlz(l, r, i);
        if (r<idx||idx<l) return;
        if (l==r) return d[i].mx=t?h[idx]:-inf, d[i].mn=t?h[idx]:inf, void();
        int md=(l+r)/2;
        open(l, md, 2*i, idx, t);
        open(md+1, r, 2*i+1, idx, t);
        d[i]=merge(d[2*i], d[2*i+1]);
    }
    void update(int l, int r, int i, int ql, int qr, int vl)
    {
        pushlz(l, r, i);
        if (r<ql||qr<l) return;
        if (ql<=l&&r<=qr) return d[i].lzmx=d[i].lzmn=vl, pushlz(l, r, i), void();
        int md=(l+r)/2;
        update(l, md, 2*i, ql, qr, vl);
        update(md+1, r, 2*i+1, ql, qr, vl);
        d[i]=merge(d[2*i], d[2*i+1]);
    }
    int query(int l, int r, int i, int ql, int qr)
    {
        pushlz(l, r, i);
        if (r<ql||qr<l) return -1;
        if (ql<=l&&r<=qr) return d[i].ans;
        int md=(l+r)/2;
        return max(query(l, md ,2*i, ql, qr), query(md+1, r, 2*i+1, ql, qr));
    }
    void show(int l, int r, int i)
    {
        pushlz(l, r, i);
        cout<<l<<' '<<r<<' '<<i<<'\n';
        cout<<"mx"<<' '<<d[i].mx<<'\n';
        cout<<"mn"<<' '<<d[i].mn<<'\n';
        cout<<"ans"<<' '<<d[i].ans<<'\n';
        if (l!=r) show(l, (l+r)/2, 2*i), show((l+r)/2+1, r, 2*i+1);
    }
} s;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n;
    for (int i=1; i<=n; i++)
    {
        cin>>h[i]>>a[i]>>b[i];
        if (i+a[i]<=n) add[i+a[i]].push_back(i);
        if (i+b[i]<=n) rem[i+b[i]].push_back(i);
    }
    cin>>q;
    for (int i=1; i<=q; i++)
    {
        cin>>l[i]>>r[i];
        qrs[r[i]].push_back(i);
    }
    for (int i=1; i<=n; i++)
    {
        for (auto x:add[i]) s.open(1, n, 1, x, 1);
        if (i-a[i]>=1) s.update(1, n, 1, max(1, i-b[i]), i-a[i], h[i]);
        for (auto x:qrs[i]) res[x]=s.query(1, n, 1, l[x], r[x]);
        for (auto x:rem[i]) s.open(1, n, 1, x, 0);
        //s.show(1, n, 1);
    }
    for (int i=1; i<=q; i++) cout<<res[i]<<'\n';
}

Compilation message (stderr)

antennas.cpp: In constructor 'segtree::node::node()':
antennas.cpp:13:32: warning: 'segtree::node::lzmn' will be initialized after [-Wreorder]
   13 |         int mx, mn, ans, lzmx, lzmn;
      |                                ^~~~
antennas.cpp:13:21: warning:   'int segtree::node::ans' [-Wreorder]
   13 |         int mx, mn, ans, lzmx, lzmn;
      |                     ^~~
antennas.cpp:14:9: warning:   when initialized here [-Wreorder]
   14 |         node(): mx(-inf), mn(inf), lzmx(-inf), lzmn(inf), ans(-1) {}
      |         ^~~~

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