Submission #750046

#	Time	Username	Problem	Language	Result	Execution time	Memory
750046		keta_tsimakuridze	Two Antennas (JOI19_antennas)	C++14	100 / 100	460 ms	31956 KiB

antennas

#include<iostream>
#include<vector>
#include<set>
#define f first
#define s second
//#define int long long
#define pii pair<int,int>
using namespace std;
const int N = 2e5 + 5, inf = 2e9; // !
int h[N];
vector<int> add[N];
vector<pair<int,int>> qry[N];
struct node {
    int mx, mn, ans;
} t[4 * N];
struct lazy {
    int mn, mx;
} lz[4 * N];
node merge(node a, node b) {
    return {max(a.mx, b.mx), min(a.mn, b.mn), max(a.ans, b.ans)};
}
void build(int u, int l, int r) {
    lz[u] = {inf, 0};
    if(l == r) {
        t[u] = { 0, inf, -inf};
        return;
    }
    int mid = (l + r) / 2;
    build(2 * u, l, mid); build(2 * u + 1, mid + 1, r);
    t[u] = merge(t[2 * u], t[2 * u + 1]);
}
void push(int u, int l, int r) {

    t[u].ans = max(t[u].ans, lz[u].mx - t[u].mn);
    t[u].ans = max(t[u].ans, t[u].mx - lz[u].mn);
    if(l != r) {
        for(int t = 0; t <= 1; t++)
            lz[2 * u + t].mx = max(lz[2 * u + t].mx, lz[u].mx),
                    lz[2 * u + t].mn = min(lz[2 * u + t].mn, lz[u].mn);
    }
    lz[u] = {inf, 0};
}
void upd(int u, int id, int l, int r) {
    if(lz[u].mx) push(u, l, r);
    if(l > id || r < id) return;
    if(l == r) {
        if(t[u].mx) t[u].mx = 0, t[u].mn = inf;
        else t[u].mx = h[l], t[u].mn = h[r];
        return;
    }
    int mid = (l + r) / 2;
    upd(2 * u, id, l, mid); upd(2 * u + 1, id, mid + 1, r);
    t[u] = merge(t[2 * u], t[2 * u + 1]);
}
void upd(int u, int st, int en, int l, int r, int val) {
    if(lz[u].mx) push(u, l, r);
    if(l > en || r < st) return;
    if(st <= l && r <= en) {
        lz[u] = {val, val};
        push(u, l, r);
        return;
    }
    int mid = (l + r) / 2;
    upd(2 * u, st, en, l, mid, val);
    upd(2 * u + 1, st, en, mid + 1, r, val);
    t[u] = merge(t[2 * u], t[2 * u + 1]);
}
int get(int u, int st, int en, int l, int r) {
    if(lz[u].mx) push(u, l, r);
    if(l > en || r < st) return -inf;
    if(st <= l && r <= en) return t[u].ans;
    int mid = (l + r) / 2;
    return max(get(2 * u, st, en, l, mid), get(2 * u + 1, st, en, mid + 1, r));
}
signed main() {
    ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int n;
    cin >> n;
    vector<int> l(n + 2), r(n + 2);
    for(int i = 1; i <= n; i++) {
        cin >> h[i] >> l[i] >> r[i];
        if(i + l[i] <= n) add[i + l[i]].push_back(i), add[min(i + r[i] + 1, n + 1)].push_back(i);
    }
    build(1, 1, n);
    int q; cin >> q;
    for(int i = 1; i <= q; i++) {
        int l, r; cin >> l >> r;
        qry[r].push_back({l, i});
    }
    vector<int> ans(q + 1);
    for(int i = 1; i <= n; i++) {
        for(int j = 0; j < add[i].size(); j++) {
            upd(1, add[i][j], 1, n); 
        }
        upd(1, i - r[i], i - l[i], 1, n, h[i]);
        for(int j = 0; j < qry[i].size(); j++) ans[qry[i][j].s] = get(1, qry[i][j].f, i, 1, n);
    }
    for(int i = 1; i <= q; i++) cout << (ans[i] < 0 ? -1 : ans[i]) << "\n";
}

Compilation message (stderr)

antennas.cpp: In function 'int main()':
antennas.cpp:92:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |         for(int j = 0; j < add[i].size(); j++) {
      |                        ~~^~~~~~~~~~~~~~~
antennas.cpp:96:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |         for(int j = 0; j < qry[i].size(); j++) ans[qry[i][j].s] = get(1, qry[i][j].f, i, 1, n);
      |                        ~~^~~~~~~~~~~~~~~

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