Submission #122837

#	Time	Username	Problem	Language	Result	Execution time	Memory
122837		PeppaPig	Two Antennas (JOI19_antennas)	C++14	100 / 100	753 ms	41592 KiB

antennas

#include <bits/stdc++.h>

#define pii pair<int, int>
#define x first
#define y second

using namespace std;

const int N = 1 << 18;
const int INF = 1e9 + 1;

int n, q;

int mn[N<<1], mx[N<<1], lo[N<<1], hi[N<<1], t[N<<1];

void push(int p, int l, int r) {
    t[p] = max({t[p], hi[p] - mn[p], mx[p] - lo[p]});
    if(l != r) {
        if(mn[p<<1] != INF) {
            lo[p<<1] = min(lo[p<<1], lo[p]);
            hi[p<<1] = max(hi[p<<1], hi[p]);
        }
        if(mn[p<<1|1] != INF) {
            lo[p<<1|1] = min(lo[p<<1|1], lo[p]);
            hi[p<<1|1] = max(hi[p<<1|1], hi[p]);
        } 
    }
    lo[p] = INF, hi[p] = -INF;
}

void tag(int x, int k, int p = 1, int l = 1, int r = n) {
    push(p, l, r);
    if(l == r) {
        if(k == -1) mn[p] = INF, mx[p] = -INF;
        else mn[p] = mx[p] = k;
        return;
    }
    int mid = l + r >> 1;
    if(x <= mid) tag(x, k, p<<1, l, mid);
    else tag(x, k, p<<1|1, mid+1, r);
    mn[p] = min(mn[p<<1], mn[p<<1|1]), mx[p] = max(mx[p<<1], mx[p<<1|1]);
}

void add(int x, int y, int k, int p = 1, int l = 1, int r = n) {
    push(p, l, r);
    if(x > r || l > y) return;
    if(x <= l && r <= y) {
        if(mn[p] == INF) return;
        lo[p] = min(lo[p], k), hi[p] = max(hi[p], k);
        push(p, l, r);
        return;
    }
    int mid = l + r >> 1;
    add(x, y, k, p<<1, l, mid), add(x, y, k, p<<1|1, mid+1, r);
    t[p] = max(t[p<<1], t[p<<1|1]);
}

int query(int x, int y, int p = 1, int l = 1, int r = n) {
    push(p, l, r);
    if(x > r || l > y) return -INF;
    if(x <= l && r <= y) return t[p];
    int mid = l + r >> 1;
    return max(query(x, y, p<<1, l, mid), query(x, y, p<<1|1, mid+1, r));
}

int H[N], A[N], B[N], ans[N];
vector<int> in[N], out[N];
vector<pii> Q[N];

int main() {
    fill_n(mn, N<<1, INF), fill_n(mx, N<<1, -INF);
    fill_n(lo, N<<1, INF), fill_n(hi, N<<1, -INF);
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%d %d %d", H+i, A+i, B+i);
        if(i + A[i] <= n) in[i + A[i]].emplace_back(i);
        if(i + B[i] <= n) out[i + B[i]].emplace_back(i);
    }
    scanf("%d", &q);
    for(int i = 1, a, b; i <= q; i++) {
        scanf("%d %d", &a, &b);
        Q[b].emplace_back(a, i);
    }
    for(int i = 1; i <= n; i++) {
        for(int x : in[i]) tag(x, H[x]);
        add(i - B[i], i - A[i], H[i]);
        for(pii p : Q[i]) ans[p.y] = query(p.x, i);
        for(int x : out[i]) tag(x, -1);
    }
    for(int i = 1; i <= q; i++) {
        if(ans[i] > 0) printf("%d\n", ans[i]);
        else printf("-1\n");
    }

    return 0;
}

Compilation message (stderr)

antennas.cpp: In function 'void tag(int, int, int, int, int)':
antennas.cpp:38:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 1;
               ~~^~~
antennas.cpp: In function 'void add(int, int, int, int, int, int)':
antennas.cpp:53:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 1;
               ~~^~~
antennas.cpp: In function 'int query(int, int, int, int, int)':
antennas.cpp:62:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 1;
               ~~^~~
antennas.cpp: In function 'int main()':
antennas.cpp:73:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
antennas.cpp:75:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d", H+i, A+i, B+i);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:79:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &q);
     ~~~~~^~~~~~~~~~
antennas.cpp:81:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &a, &b);
         ~~~~~^~~~~~~~~~~~~~~~~

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