oj.uz

Submission #391171

# Submission time Handle Problem Language Result Execution time Memory
391171 2021-04-18T06:46:11 Z parsabahrami Two Antennas (JOI19_antennas) C++17
22 / 100
 465 ms 48364 KB 
/* There's someone in my head but it's not me */ 
#include <bits/stdc++.h>
 
using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;
 
#define SZ(x)                       (int) x.size()
#define F                           first
#define S                           second

const int N = 2e5 + 10;
int n, q, A[N], B[N], h[N]; ll ans[N];
struct node {
    ll ret, mn, mx, lzmn, lzmx; node *lc, *rc; 

    node() : ret(-1e18), mn(1e18), mx(-1e18), lzmn(1e18), lzmx(-1e18), lc(nullptr), rc(nullptr) {};
    
    void build(int l = 1, int r = n + 1) {
        if (r - l < 2) return;
        int md = (l + r) >> 1;
        lc = new node(), rc = new node();
        lc->build(l, md), rc->build(md, r);
    }

    void shift() {
        ret = max({ret, mx - lzmn, lzmx - mn});
        if (lc) 
            lc->lzmn = min(lc->lzmn, lzmn), lc->lzmx = max(lc->lzmx, lzmx);
        if (rc) 
            rc->lzmn = min(rc->lzmn, lzmn), rc->lzmx = max(rc->lzmx, lzmx);
        lzmx = -1e18, lzmn = 1e18;
    }

    void modify(int p, int t, int l = 1, int r = n + 1) {
        shift();
        if (r - l < 2) {
            if (!t) {
                node* x = this;
                *x = node();
            }
            else mx = mn = h[p];
            return;
        }
        int md = (l + r) >> 1;
        if (p < md) lc->modify(p, t, l, md), rc->shift();
        else rc->modify(p, t, md, r), lc->shift();
        mx = max(lc->mx, rc->mx), mn = min(lc->mn, rc->mn);
        ret = max({ret, lc->ret, rc->ret});
    }
    
    void upd(int ql, int qr, ll x, int l = 1, int r = n + 1) {
        shift();
        if (qr <= l || r <= ql || ql >= qr) return;
        if (ql <= l && r <= qr) {
            lzmn = min(lzmn, x); lzmx = max(lzmx, x);
            return shift();
        }
        int md = (l + r) >> 1;
        lc->upd(ql, qr, x, l, md), rc->upd(ql, qr, x, md, r);
        mx = max(lc->mx, rc->mx), mn = min(lc->mn, rc->mn);
        ret = max({ret, lc->ret, rc->ret});
    }

    ll get(int ql, int qr, int l = 1, int r = n + 1) {
        shift();
        if (qr <= l || r <= ql || ql >= qr) return -1e18;
        if (ql <= l && r <= qr) return ret;
        int md = (l + r) >> 1;
        return max(lc->get(ql, qr, l, md), rc->get(ql, qr, md, r));
    }
};
node* seg; vector<pii> vec[N], Q[N];

int main() {
    fill(ans, ans + N, -1e18);
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d%d", &h[i], &A[i], &B[i]);
        vec[min(n + 1, i + A[i])].push_back({i, 1});
        vec[min(n + 1, i + B[i] + 1)].push_back({i, 0});
    }
    scanf("%d", &q);
    for (int i = 1; i <= q; i++) {
        int l, r; scanf("%d%d", &l, &r);
        Q[r].push_back({l, i});
    }
    seg = new node();
    seg->build();
    for (int i = 1; i <= n; i++) {
        for (pii &j : vec[i]) {
            seg->modify(j.F, j.S);
        }
        seg->upd(i - B[i], i - A[i] + 1, h[i]);
        for (pii &j : Q[i]) 
            ans[j.S] = seg->get(j.F, i + 1);
    }
    for (int i = 1; i <= q; i++) 
        printf("%lld\n", ans[i] > -1e18 ? ans[i] : -1ll);
    return 0;
}

Compilation message

antennas.cpp: In function 'int main()':
antennas.cpp:78:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   78 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
antennas.cpp:80:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   80 |         scanf("%d%d%d", &h[i], &A[i], &B[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:84:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   84 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
antennas.cpp:86:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   86 |         int l, r; scanf("%d%d", &l, &r);
      |                   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 2.0

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

Subtask #2
0 / 11.0

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

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 355 ms 44484 KB Output is correct
2 Correct 413 ms 48288 KB Output is correct
3 Correct 305 ms 37140 KB Output is correct
4 Correct 403 ms 48348 KB Output is correct
5 Correct 151 ms 28180 KB Output is correct
6 Correct 389 ms 48364 KB Output is correct
7 Correct 336 ms 43324 KB Output is correct
8 Correct 465 ms 48288 KB Output is correct
9 Correct 50 ms 17060 KB Output is correct
10 Correct 390 ms 48276 KB Output is correct
11 Correct 223 ms 34352 KB Output is correct
12 Correct 396 ms 48240 KB Output is correct
13 Correct 279 ms 46536 KB Output is correct
14 Correct 253 ms 46672 KB Output is correct
15 Correct 244 ms 46632 KB Output is correct
16 Correct 224 ms 47028 KB Output is correct
17 Correct 273 ms 46604 KB Output is correct
18 Correct 249 ms 46900 KB Output is correct
19 Correct 261 ms 46544 KB Output is correct
20 Correct 258 ms 46556 KB Output is correct
21 Correct 237 ms 46372 KB Output is correct
22 Correct 257 ms 46700 KB Output is correct
23 Correct 259 ms 46516 KB Output is correct
24 Correct 221 ms 46632 KB Output is correct

Subtask #4
0 / 65.0

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