Submission #1097636

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097636		thangdz2k7	Two Antennas (JOI19_antennas)	C++17	0 / 100	82 ms	50876 KiB

antennas

// author : thembululquaUwU
// 3.9.2024

#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define endl '\n'

using namespace std;
using ll = long long;
using ii = pair <int, int>;
using vi = vector <int>;

const int N = 2e5 + 5;
const int mod = 1e9 + 7;

void maxl(auto &a, auto b) {a = max(a, b);}
void minl(auto &a, auto b) {a = min(a, b);}

int n, q, h[N], a[N], b[N], ans[N];
vector <ii> query[N], event[N];
int T[N << 2], mx[N << 2], mn[N << 2];

void pull(int s, bool op){
    maxl(T[s], mx[s] - mn[s]);
    if (op){
        maxl(mx[s << 1], mx[s]);
        maxl(mx[s << 1 | 1], mx[s]);
        mx[s] = 0;
    }
}

void update_Point(int u, int val, int s = 1, int l = 1, int r = n){
    pull(s, l < r);
    if (l == r){
        mn[s] = val; return;
    }

    int mid = l + r >> 1;
    if (mid >= u) update_Point(u, val, s << 1, l, mid);
    else update_Point(u, val, s << 1 | 1, mid + 1, r);
    mn[s] = min(mn[s << 1], mn[s << 1 | 1]);
}

void update_Range(int u, int v, int val, int s = 1, int l = 1, int r = n){
    pull(s, l < r);
    if (u <= l && r <= v){
        mx[s] = val; pull(s, l < r); return;
    }

    int mid = l + r >> 1;
    if (mid >= u) update_Range(u, v, val, s << 1, l, mid);
    if (mid < v) update_Range(u, v, val, s << 1 | 1, mid + 1, v);
    T[s] = max(T[s << 1], T[s << 1 | 1]);
}

int get(int u, int v, int s = 1, int l = 1, int r = n){
    pull(s, l < r);
    if (u > r || v < l) return -1;
    if (u <= l && r <= v) return T[s];

    int mid = l + r >> 1;
    return max(get(u, v, s << 1, l, mid), get(u, v, s << 1 | 1, mid + 1, r));
}

void solve(){
    for (int i = 1; i <= 4 * n; ++ i) T[i] = -1, mx[i] = 0, mn[i] = mod;

    for (int i = 1; i <= n; ++ i){
        if (i + a[i] <= n) event[i + a[i]].emplace_back(i, h[i]);
        if (i + b[i] + 1 <= n) event[i + b[i] + 1].emplace_back(i, mod);
    }

    for (int r = 1; r <= n; ++ r){
        for (auto [id, val] : event[r]) update_Point(id, val);
        int u = max(1, r - b[r]), v = max(0, r - a[r]);
        if (u <= v) update_Range(u, v, h[r]);
        for (auto [l, id] : query[r]) maxl(ans[id], get(l, r));
        event[r].clear();
    }
}

int main(){
    if (fopen("pqh.inp", "r")){
        freopen("pqh.inp", "r", stdin);
        freopen("pqh.out", "w", stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n;
    for (int i = 1; i <= n; ++ i) cin >> h[i] >> a[i] >> b[i];
    int q; cin >> q;
    for (int i = 1; i <= q; ++ i){
        int l, r; cin >> l >> r;
        query[r].emplace_back(l, i);
        ans[i] = -1;
    }

    solve(); for (int i = 1; i <= n; ++ i) h[i] = mod - h[i];
    solve(); for (int i = 1; i <= q; ++ i) cout << ans[i] << endl;

    return 0;
}

Compilation message (stderr)

antennas.cpp:18:11: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   18 | void maxl(auto &a, auto b) {a = max(a, b);}
      |           ^~~~
antennas.cpp:18:20: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   18 | void maxl(auto &a, auto b) {a = max(a, b);}
      |                    ^~~~
antennas.cpp:19:11: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   19 | void minl(auto &a, auto b) {a = min(a, b);}
      |           ^~~~
antennas.cpp:19:20: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   19 | void minl(auto &a, auto b) {a = min(a, b);}
      |                    ^~~~
antennas.cpp: In function 'void update_Point(int, int, int, int, int)':
antennas.cpp:40:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   40 |     int mid = l + r >> 1;
      |               ~~^~~
antennas.cpp: In function 'void update_Range(int, int, int, int, int, int)':
antennas.cpp:52:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |     int mid = l + r >> 1;
      |               ~~^~~
antennas.cpp: In function 'int get(int, int, int, int, int)':
antennas.cpp:63:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   63 |     int mid = l + r >> 1;
      |               ~~^~~
antennas.cpp: In function 'int main()':
antennas.cpp:86:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |         freopen("pqh.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:87:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |         freopen("pqh.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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