Submission #1169904

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169904		nekolie	Two Antennas (JOI19_antennas)	C++20	0 / 100	28 ms	6720 KiB

antennas

// Karusia + Miki 2025 (totalnie)
#include <bits/stdc++.h>
using namespace std;

const int baza = (1<<18);
int inf = 1000000007, d[2*baza][2];
int min_query(int a, int b) {
    int wynik = inf;
    a += baza-1, b += baza+1;
    while (a/2 != b/2) {
        if (a%2 == 0)
            wynik = min(wynik,d[a+1][0]);
        if (b%2 == 1)
            wynik = min(wynik,d[b-1][0]);
        a /= 2, b /= 2;
    }
    return wynik;
}
int max_query(int a, int b) {
    int wynik = -inf;
    a += baza-1, b += baza+1;
    while (a/2 != b/2) {
        if (a%2 == 0)
            wynik = max(wynik,d[a+1][1]);
        if (b%2 == 1)
            wynik = max(wynik,d[b-1][1]);
        a /= 2, b /= 2;
    }
    return wynik;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    for (int i = 1; i < 2*baza; i++)
        d[i][0] = inf, d[i][1] = -inf;
    int n,q; cin >> n;
    int ant[n][3], l, r, odp = -1;
    for (int i = 0; i < n; i++)
        cin >> ant[i][0] >> ant[i][1] >> ant[i][2], d[i+baza][0] = d[i+baza][1] = ant[i][0];
    for (int i = baza-1; i > 0; i--)
        d[i][0] = min(d[2*i][0],d[2*i+1][0]), d[i][1] = max(d[2*i][1],d[2*i+1][1]);
    cin >> q >> l >> r, assert(q == 1 && l == 1 && q == n);
    for (int i = 0; i < n; i++) {
        int mini = inf, maks = -inf;
        if (ant[i][0]-ant[i][2] >= 0)
            mini = min(mini,min_query(ant[i][0]-ant[i][2],ant[i][0]-ant[i][1])), maks = max(maks,max_query(ant[i][0]-ant[i][2],ant[i][0]-ant[i][1]));
        else if (ant[i][0]-ant[i][1] >= 0)
            mini = min(mini,min_query(0,ant[i][0]-ant[i][1])), maks = max(maks,max_query(0,ant[i][0]-ant[i][1]));
        if (ant[i][0]+ant[i][2] < n)
            mini = min(mini,min_query(ant[i][0]+ant[i][1],ant[i][0]+ant[i][2])), maks = max(maks,max_query(ant[i][0]+ant[i][1],ant[i][0]+ant[i][2]));
        else if (ant[i][0]+ant[i][1] < n)
            mini = min(mini,min_query(ant[i][0]+ant[i][1],n-1)), maks = max(maks,max_query(ant[i][0]+ant[i][1],n-1));
        odp = max({odp,ant[i][0]-mini,maks-ant[i][0]});
    }
    cout << odp << endl;
    return 0;
}

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