Submission #128359

#	Time	Username	Problem	Language	Result	Execution time	Memory
128359		RezwanArefin01	Two Antennas (JOI19_antennas)	C++17	0 / 100	541 ms	43904 KiB

antennas

///usr/bin/g++ -O2 $0 -o ${0%.cpp} && echo "----------" && ./${0%.cpp}; exit;
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> ii; 

const int N = 2e5 + 5; 
const int inf = 1e9+7;
int n, h[N], a[N], b[N], q, l[N], r[N], ans[N]; 
vector<int> events[N + N];;
vector<ii>  Q[N];

struct node {
    int dp, h, x, lazy; 
    node(int dp = -inf, int h = -inf, int x = inf):
        dp(dp), h(h), x(x), lazy(inf) {}
} t[N << 2];

void upd(int node, int x) {
    t[node].x = min(t[node].x, x); 
    t[node].dp = max(t[node].dp, t[node].h - t[node].x); 
}

void shift(int node) {
    if(t[node].lazy == inf) return; 
    upd(node << 1, t[node].lazy); 
    upd(node << 1 | 1, t[node].lazy); 
    t[node].lazy = inf; 
}
void seth(int node, int l, int r, int i, int H) {
    if(l == r) {
        t[node].h = H; 
        t[node].dp = H - t[node].x;
        return; 
    }
    int m = l + r >> 1; 
    if(i <= m) seth(node << 1, l, m, i, H); 
    else seth(node << 1 | 1, m + 1, r, i, H); 
    t[node].h = max(t[node << 1].h, t[node << 1 | 1].h);
}

void setx(int node, int l, int r, int i, int j, int x) {
    if(r < i || l > j || x > t[node].x || t[node].h == -inf) return; 
    if(i <= l && r <= j) {
        upd(node, x); 
        return; 
    }
    shift(node); 
    int m = l + r >> 1; 
    setx(node << 1, l, m, i, j, x); 
    setx(node << 1 | 1, m + 1, r, i, j, x); 
    t[node].dp = max(t[node << 1].dp, t[node << 1 | 1].dp); 

}

int get(int node, int l, int r, int i, int j) {
    if(r < i || l > j) return -1; 
    if(i <= l && r <= j) return t[node].dp; 
    shift(node);
    int m = l + r >> 1; 
    return max(get(node << 1, l, m, i, j), 
        get(node << 1 | 1, m + 1, r, i, j)); 
}
void run() {
    for(int i = 1; i <= q; ++i) 
        Q[r[i]].emplace_back(l[i], i); 

    for(int i = 1; i <= n; ++i) {
        events[i + a[i]].push_back(i); 
        events[i + b[i] + 1].push_back(-i); 

        for(int j : events[i]) {
            if(j > 0) {
                seth(1, 1, n, j, h[j]); 
            } else {
                seth(1, 1, n, -j, -inf); 
            }
        }

        if(i > a[i]) 
            setx(1, 1, n, max(1, i - b[i]), i - a[i], h[i]); 

        for(auto &it : Q[i]) {
            ans[it.second] = max(ans[it.second], get(1, 1, n, it.first, i)); 
        }
    }
}

int main(int argc, char const *argv[]) {
    scanf("%d", &n); 
    for(int i = 1; i <= n; ++i) {
        scanf("%d %d %d", &h[i], &a[i], &b[i]); 
    }    
    scanf("%d", &q); 
    for(int i = 1; i <= q; ++i) {
        scanf("%d %d", &l[i], &r[i]); 
        ans[i] = -1; 
    }

    run(); 

    reverse(h + 1, h + n + 1); 
    reverse(a + 1, a + n + 1); 
    reverse(b + 1, b + n + 1); 

    for(int i = 1; i <= q; ++i) {
        l[i] = n + 1 - l[i];
        r[i] = n + 1 - r[i]; 
        swap(l[i], r[i]);
    }

    for(int i = 1; i <= 4 * n; ++i) 
        t[i] = node(); 
    for(int i = 1; i <= n; ++i) {
        Q[i].clear(); 
        events[i].clear(); 
    }

    run();

    for(int i = 1; i <= q; ++i) {
        printf("%d\n", ans[i]);
    }

}

Compilation message (stderr)

antennas.cpp: In function 'void seth(int, int, int, int, int)':
antennas.cpp:37:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int m = l + r >> 1; 
             ~~^~~
antennas.cpp: In function 'void setx(int, int, int, int, int, int)':
antennas.cpp:50:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int m = l + r >> 1; 
             ~~^~~
antennas.cpp: In function 'int get(int, int, int, int, int)':
antennas.cpp:61:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int m = l + r >> 1; 
             ~~^~~
antennas.cpp: In function 'int main(int, const char**)':
antennas.cpp:91:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n); 
     ~~~~~^~~~~~~~~~
antennas.cpp:93: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:95:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &q); 
     ~~~~~^~~~~~~~~~
antennas.cpp:97:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &l[i], &r[i]); 
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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