Submission #361827

#	Time	Username	Problem	Language	Result	Execution time	Memory
361827		Vanjanja	Two Antennas (JOI19_antennas)	C++14	100 / 100	1127 ms	33696 KiB

antennas

#include <bits/stdc++.h>
using namespace std;

const int N = 2 * 1e5, inf = 1e9 + 7;
int a[N];
pair<int, int> b[N];
vector<pair<int, int>> que[N];
int resenje[N];
int segDP[4 * N], segM[4 * N][2];
pair<int, int> lazy[4 * N];

void build(int u, int l, int r) {
    segDP[u] = -1, lazy[u].second = inf;
    segM[u][0] = -inf, segM[u][1] = inf;
    if (l == r)
        return;
    int mid = l + r >> 1;
    build(u*2+1,l,mid);
    build(u*2+2,mid+1,r);
}

void update1(int u, int x) {
    if (segM[u][0] == -inf)
        return;
    segDP[u] = max(segDP[u], max(abs(x - segM[u][0]), abs(x - segM[u][1])));
    lazy[u].first = max(lazy[u].first, x);
    lazy[u].second = min(lazy[u].second, x);
}

void shift(int u) {
    if (lazy[u].first) {
        update1(u*2+1,lazy[u].first);
        update1(u*2+2,lazy[u].first);
        lazy[u].first = 0;
    }
    if (lazy[u].second != inf) {
        update1(u*2+1,lazy[u].second);
        update1(u*2+2,lazy[u].second);
        lazy[u].second = inf;
    }
}

void update(int u, int l, int r, int L, int R, int x) {
    if (l > R || r < L)
        return;
    if (l >= L && r <= R) {
        update1(u, x);
        return;
    }
    shift(u);
    int mid = l + r >> 1;
    update(u*2+1,l,mid,L,R,x);
    update(u*2+2,mid+1,r,L,R,x);
    segDP[u] = max(segDP[u*2+1],segDP[u*2+2]);
}

void add(int u, int l, int r, int i, bool p) {
    if (l == r) {
        if (p) {
            segM[u][0] = a[i];
            segM[u][1] = a[i];
            return;
        }
        segM[u][0] = -inf;
        segM[u][1] = inf;
        return;
    }
    shift(u);
    int mid = l + r >> 1;
    if (l <= i && i <= mid)
        add(u*2+1, l, mid, i, p);
    else
        add(u*2+2, mid+1, r, i, p);
    segM[u][0] = max(segM[u*2+1][0], segM[u*2+2][0]);
    segM[u][1] = min(segM[u*2+1][1], segM[u*2+2][1]);
}

int out(int u, int l, int r, int L, int R) {
    if (l > R || r < L)
        return -1;
    if (l >= L && r <= R) {
        return segDP[u] == -inf? -1:segDP[u];
    }
    shift(u);
    int mid = l + r >> 1;
    return max(out(u*2+1,l,mid,L,R), out(u*2+2,mid+1,r,L,R));
}

void solve() {
    int n, q;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i] >> b[i].first >> b[i].second;
    }
    cin >> q;
    for (int i = 0; i < q; i++) {
        int l, r;
        cin >> l >> r;
        que[l - 1].push_back({r - 1, i});
    }
    build(0, 0, n - 1);
    priority_queue<pair<int, int>> d;
    priority_queue<pair<int, int>> l;
    for (int i = n - 1; i >= 0; i--) {
        while (d.size() && d.top().first >= i) {
            add(0, 0, n - 1, d.top().second, 1);
            l.push({d.top().second - b[d.top().second].second, d.top().second});
            d.pop();
        }
        while (l.size() && l.top().first > i) {
            add(0, 0, n - 1, l.top().second, 0);
            l.pop();
        }
        update(0, 0, n - 1, i + b[i].first, min(i + b[i].second, n - 1), a[i]);
        d.push({i - b[i].first, i});
        for (auto j = que[i].begin(); j != que[i].end(); j++) {
            resenje[(*j).second] = out(0, 0, n - 1, i, (*j).first);
        }
    }
    for (int i = 0; i < q; i++)
        cout << resenje[i] << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}

Compilation message (stderr)

antennas.cpp: In function 'void build(int, int, int)':
antennas.cpp:17:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   17 |     int mid = l + r >> 1;
      |               ~~^~~
antennas.cpp: In function 'void update(int, int, int, int, int, int)':
antennas.cpp:51:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   51 |     int mid = l + r >> 1;
      |               ~~^~~
antennas.cpp: In function 'void add(int, int, int, int, bool)':
antennas.cpp:69:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   69 |     int mid = l + r >> 1;
      |               ~~^~~
antennas.cpp: In function 'int out(int, int, int, int, int)':
antennas.cpp:85:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   85 |     int mid = l + r >> 1;
      |               ~~^~~

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