oj.uz

Submission #128360

# Submission time Handle Problem Language Result Execution time Memory
128360 2019-07-10T19:14:58 Z RezwanArefin01 Two Antennas (JOI19_antennas) C++17
0 / 100
 506 ms 39376 KB 
///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; 
        return; 
    }
    shift(node); 
    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 -inf; 
    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[]) {
#ifdef LOCAL
    freopen("in", "r", stdin);
#endif
    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

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

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 27000 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 27000 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 459 ms 38108 KB Output is correct
2 Correct 506 ms 39308 KB Output is correct
3 Correct 353 ms 35560 KB Output is correct
4 Correct 500 ms 39292 KB Output is correct
5 Correct 210 ms 32632 KB Output is correct
6 Correct 489 ms 39288 KB Output is correct
7 Correct 432 ms 37652 KB Output is correct
8 Correct 484 ms 39376 KB Output is correct
9 Correct 73 ms 28920 KB Output is correct
10 Correct 494 ms 39372 KB Output is correct
11 Incorrect 294 ms 34652 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 65.0

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 27000 KB Output isn't correct
2 Halted 0 ms 0 KB -