Submission #391186

#	Time	Username	Problem	Language	Result	Execution time	Memory
391186		parsabahrami	Two Antennas (JOI19_antennas)	C++17	100 / 100	770 ms	56552 KiB

antennas

/* There's someone in my head but it's not me */ 
#include <bits/stdc++.h>
 
using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;
 
#define SZ(x)                       (int) x.size()
#define F                           first
#define S                           second

const int N = 2e5 + 10;
int n, q, A[N], B[N], h[N]; ll ans[N];
struct node {
    ll ret, mn, mx, lzmn, lzmx; node *lc, *rc; 

    node() : ret(-1), mn(1e18), mx(-1e18), lzmn(1e18), lzmx(-1e18), lc(nullptr), rc(nullptr) {};
    
    void build(int l = 1, int r = n + 1) {
        if (r - l < 2) return;
        int md = (l + r) >> 1;
        lc = new node(), rc = new node();
        lc->build(l, md), rc->build(md, r);
    }

    void shift() {
        ret = max({ret, mx - lzmn, lzmx - mn});
        if (lc) 
            lc->lzmn = min(lc->lzmn, lzmn), lc->lzmx = max(lc->lzmx, lzmx);
        if (rc) 
            rc->lzmn = min(rc->lzmn, lzmn), rc->lzmx = max(rc->lzmx, lzmx);
        lzmx = -1e18, lzmn = 1e18;
    }

    void modify(int p, int t, int l = 1, int r = n + 1) {
        shift();
        if (r - l < 2) {
            if (!t) mx = -1e18, mn = 1e18;
            else mx = mn = h[p];
            return;
        }
        int md = (l + r) >> 1;
        if (p < md) lc->modify(p, t, l, md), rc->shift();
        else rc->modify(p, t, md, r), lc->shift();
        mx = max(lc->mx, rc->mx), mn = min(lc->mn, rc->mn);
        ret = max(lc->ret, rc->ret);
    }
    
    void upd(int ql, int qr, ll x, int l = 1, int r = n + 1) {
        shift();
        if (qr <= l || r <= ql || ql >= qr) return;
        if (ql <= l && r <= qr) {
            lzmn = min(lzmn, x); lzmx = max(lzmx, x);
            return shift();
        }
        int md = (l + r) >> 1;
        lc->upd(ql, qr, x, l, md), rc->upd(ql, qr, x, md, r);
        mx = max(lc->mx, rc->mx), mn = min(lc->mn, rc->mn);
        ret = max(lc->ret, rc->ret);
    }

    ll get(int ql, int qr, int l = 1, int r = n + 1) {
        shift();
        if (qr <= l || r <= ql || ql >= qr) return -1;
        if (ql <= l && r <= qr) return ret;
        int md = (l + r) >> 1;
        return max(lc->get(ql, qr, l, md), rc->get(ql, qr, md, r));
    }
};
node* seg; vector<pii> vec[N], Q[N];

int main() {
    fill(ans, ans + N, -1);
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d%d", &h[i], &A[i], &B[i]);
        vec[min(n + 1, i + A[i])].push_back({i, 1});
        vec[min(n + 1, i + B[i] + 1)].push_back({i, 0});
    }
    scanf("%d", &q);
    for (int i = 1; i <= q; i++) {
        int l, r; scanf("%d%d", &l, &r);
        Q[r].push_back({l, i});
    }
    seg = new node();
    seg->build();
    for (int i = 1; i <= n; i++) {
        for (pii &j : vec[i]) {
            seg->modify(j.F, j.S);
        }
        seg->upd(i - B[i], i - A[i] + 1, h[i]);
        for (pii &j : Q[i]) 
            ans[j.S] = seg->get(j.F, i + 1);
    }
    for (int i = 1; i <= q; i++) 
        printf("%lld\n", ans[i]);
    return 0;
}

Compilation message (stderr)

antennas.cpp: In function 'int main()':
antennas.cpp:75:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   75 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
antennas.cpp:77:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   77 |         scanf("%d%d%d", &h[i], &A[i], &B[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:81:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   81 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
antennas.cpp:83:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   83 |         int l, r; scanf("%d%d", &l, &r);
      |                   ~~~~~^~~~~~~~~~~~~~~~

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