oj.uz

Submission #391176

# Submission time Handle Problem Language Result Execution time Memory
391176 2021-04-18T06:56:24 Z parsabahrami Two Antennas (JOI19_antennas) C++17
22 / 100
 425 ms 44192 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 8 ms 11268 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 11268 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 362 ms 40800 KB Output is correct
2 Correct 408 ms 44100 KB Output is correct
3 Correct 260 ms 34608 KB Output is correct
4 Correct 410 ms 44172 KB Output is correct
5 Correct 162 ms 26804 KB Output is correct
6 Correct 408 ms 44144 KB Output is correct
7 Correct 346 ms 39856 KB Output is correct
8 Correct 409 ms 44080 KB Output is correct
9 Correct 47 ms 16824 KB Output is correct
10 Correct 425 ms 44168 KB Output is correct
11 Correct 237 ms 31920 KB Output is correct
12 Correct 424 ms 44192 KB Output is correct
13 Correct 271 ms 42416 KB Output is correct
14 Correct 254 ms 42644 KB Output is correct
15 Correct 257 ms 42680 KB Output is correct
16 Correct 219 ms 42920 KB Output is correct
17 Correct 272 ms 42480 KB Output is correct
18 Correct 258 ms 42992 KB Output is correct
19 Correct 259 ms 42448 KB Output is correct
20 Correct 250 ms 42580 KB Output is correct
21 Correct 242 ms 42412 KB Output is correct
22 Correct 253 ms 42552 KB Output is correct
23 Correct 262 ms 42572 KB Output is correct
24 Correct 221 ms 42460 KB Output is correct

Subtask #4
0 / 65.0

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