Submission #1084226

#	Time	Username	Problem	Language	Result	Execution time	Memory
1084226		anhthi	Two Antennas (JOI19_antennas)	C++14	100 / 100	431 ms	72024 KiB

antennas

#include <bits/stdc++.h>
 
using namespace std;
 
#define fi first
#define se second
#define ll long long
#define pll pair<ll, ll>
#define pii pair<int, int>
#define mp(x, y) make_pair(x, y)
#define sz(v) ((int) (v).size())
#define all(v) (v).begin(), (v).end()
#define MASK(i) (1LL << (i))
#define BIT(x, y) (((x) >> (y)) & 1)
#define clz __builtin_clzll
#define ctz __builtin_ctzll
#define popcount __builtin_popcount
#define lg(x) (63 - clz(x))
#define max_rng *max_element
#define min_rng *min_element
 
template <class X, class Y>
    inline bool maximize(X &x, Y y) {
        return (x < y ? x = y, true : false);
    }
template <class X, class Y>
    inline bool minimize(X &x, Y y) {
        return (x > y ? x = y, true : false);
    }
template <class X>
    inline void compress(vector<X> &a) {
        sort(all(a)); a.resize(unique(all(a)) - a.begin());
    }
 
const ll oo = (ll) 1e18, inf = (int) 1e9, mod = (int) 1e9 + 19972207;
const int mxn = (int) 2e5 + 10, mxm = (int) 1e6 + 5, S = (int) 450, S2 = (int) 450, lg = (int) 18;
 
int n, q;
struct anten {
    ll h, a, b;
    void input() {
        cin >> h >> a >> b;
    }
} a[mxn];
 
struct node {
    ll ans;
    ll Max, Min;
 
    ll lzMax, lzMin;
 
    node() {
        ans = -1;
        Min = oo;
        Max = -oo;
        lzMin = oo;
        lzMax = -oo;
    }
    node(ll a, ll b, ll c) : ans(a), Max(b), Min(c) {
        // lzMin = = oo; lzMin = -oo;
    };
    node operator + (const node &o) const {
        // node res = *this;
        return node(max(ans, o.ans), max(Max, o.Max), min(Min, o.Min));
    }
};
 
struct seg {
    int n;
    vector<node> st;
 
    seg(int n) : n(n) {
        st.resize(n << 2);
    }       
 
    void setMax(int i, ll d) {
        maximize(st[i].lzMax, d);
        maximize(st[i].ans, d - st[i].Min);
        return;
    }
    void setMin(int i, ll d) {
        minimize(st[i].lzMin, d);
        maximize(st[i].ans, st[i].Max - d);
        return;
    }
    
    void down(int i) {
        if (st[i].lzMax != -oo) {
            // cout << "ya\n";
            setMax(2 * i, st[i].lzMax);
            setMax(2 * i + 1, st[i].lzMax);
            st[i].lzMax = -oo;
        }
        if (st[i].lzMin != oo) {
            // cout << "yaa\n";
            setMin(2 * i, st[i].lzMin);
            setMin(2 * i + 1, st[i].lzMin);
            st[i].lzMin = oo;
        }
        return;
    }
 
    void toggle(int p) {
        // cout << "Toggled: " << p << ' ';
        int i = 1; 
        for (int l = 1, r = n; l < r; ) {
            down(i);
            int m = (l + r) >> 1;
            if (p > m) {
                l = m + 1;
                i = 2 * i + 1;
            }
            else {
                r = m;
                i = 2 * i;
            }
        }
        if (st[i].Max != -oo) {
            // cout << "Off\n";
            st[i].Max = -oo; st[i].Min = oo;
        }
        else {
            // printf("On %d\n", a[p].h);
            st[i].Max = st[i].Min = a[p].h;
        }
        // cout << i << ' ' << st[i].ans << "\n";
        while (i > 1) {
            i >>= 1;
            st[i].Max = max(st[2 * i].Max, st[2 * i + 1].Max);
            st[i].Min = min(st[2 * i].Min, st[2 * i + 1].Min);
            st[i].ans = max(st[2 * i].ans, st[2 * i + 1].ans);
            // cout << st[i].Max << ' ' << st[i].Min << ' ' << 2 * i << ' ' << st[2 * i].ans << ' ' << 2 * i + 1 << ' ' << st[2 * i + 1].ans << '\n';
        }
        // cout << st[i].ans << '\n';
        // cout << '\n';
        return;
    }
 
    void upd(int i, int l, int r, int u, int v, ll x) {
        if (l > v || r < u) return;
        if (l >= u && r <= v) {
            // cout << i << ' ' << l << ' ' << r << ' ' << x << ' ' << st[i].Max << ' ' << st[i].Min << ' ' << st[i].ans << ' ';
            setMax(i, x); setMin(i, x);
            // cout << st[i].ans << '\n';
            return;
        }
        down(i);
        int m = (l + r) >> 1;
        upd(2 * i, l, m, u, v, x);
        upd(2 * i + 1, m + 1, r, u, v, x);
        // st[i] = st[2 * i] + st[2 * i + 1];
        st[i].Max = max(st[2 * i].Max, st[2 * i + 1].Max);
        st[i].Min = min(st[2 * i].Min, st[2 * i + 1].Min);
        st[i].ans = max(st[2 * i].ans, st[2 * i + 1].ans);
    }
 
    void upd(int u, int v, ll x) { 
        if (v < 1 || u > v) return;
        maximize(u, 1);
        // printf("Update range [%d, %d]", u, v);
        // cout << " with " << x << '\n'; 
        return upd(1, 1, n, u, v, x);
    }
 
    ll get(int i, int l, int r, int u, int v) {
        if (l > v || r < u) return -oo;
        if (l >= u && r <= v) return st[i].ans;
        down(i);
        int m = (l + r) >> 1;
        ll L = get(2 * i, l, m, u, v);
        ll R = get(2 * i + 1, m + 1, r, u, v);
        return max(L, R);
    }
 
    ll get(int u, int v) {
        return get(1, 1, n, u, v);
    }
 
};
 
vector<int> events[mxn << 1];
vector<pair<int, int>> query[mxn + 5];
 
void solve() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        a[i].input();
        events[i + a[i].a].push_back(i);
        events[i + a[i].b + 1].push_back(i);
    }
    cin >> q;
    for (int i = 1; i <= q; ++i) {
        int l, r;
        cin >> l >> r;
        query[r].push_back(mp(l, i));
    }
    seg s(n);
    vector<ll> res(q+5, -1);
    for (int i = 1; i <= n; ++i) {
        // printf("Phase begin i = %d\n", i);
        for (int e : events[i]) s.toggle(e);
        s.upd(i - a[i].b, i - a[i].a, a[i].h);
        for (pair<int, int> qID : query[i]) {
            // printf("Solved query #%d [%d, %d] = %d\n", qID.se, qID.fi, i, s.get(qID.fi, i)); 
            maximize(res[qID.se], s.get(qID.fi, i));
        }
        // printf("Phase ended\n\n");
    }
    for (int i = 1; i <= q; ++i) cout << (res[i] == -oo ? -1 : res[i]) << '\n';
}
 
int main() {
 
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
 
    #define TASK "digits"
    if (fopen(TASK".inp", "r")) {
        freopen(TASK".inp", "r", stdin);
        freopen(TASK".out", "w", stdout);
    }
 
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
 
    cerr << "\nTime elapsed: " << (1.0 * clock() / CLOCKS_PER_SEC) << " ms.";
 
    return 0;
}

Compilation message (stderr)

antennas.cpp: In function 'int main()':
antennas.cpp:219:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  219 |         freopen(TASK".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:220:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  220 |         freopen(TASK".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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