oj.uz

Submission #122821

# Submission time Handle Problem Language Result Execution time Memory
122821 2019-06-29T10:41:04 Z win11905 Two Antennas (JOI19_antennas) C++11
24 / 100
 3000 ms 330604 KB 
#include <bits/stdc++.h>
#define iii tuple<int, int, int>
using namespace std;

const int N = 1<<18;
const int INF = 1e9+1;

int n, m;
int H[N], x[N], y[N];
vector<int> preadd[N], predel[N];

struct node {
    int mn, mx;
    node *l, *r;
    node(int mn, int mx, node *l, node *r) : mn(mn), mx(mx), l(l), r(r) {}
};

node* newson(int mn, int mx) { return new node(mn, mx, nullptr, nullptr); }
node * newpar(node *l, node *r) { return new node(min(l->mn, r->mn), max(l->mx, r->mx), l, r); }

node* build(int l = 1, int r = n) {
    if(l == r) return newson(INF, -INF);
    int m = (l + r) >> 1;
    return newpar(build(l, m), build(m+1, r));
}

node* update(int v, bool st, node* p, int l = 1, int r = n) {
    if(l == r) {
        if(st) return newson(H[v], H[v]);
        return newson(INF, -INF);
    }
    int m = (l + r) >> 1;
    if(v <= m) return newpar(update(v, st, p->l, l, m), p->r);
    return newpar(p->l, update(v, st, p->r, m+1, r));
}

int qmin(int x, int y, node* p, int l = 1, int r = n) {
    if(x > r || l > y) return INF;
    if(x <= l && r <= y) return p->mn;
    int m = (l + r) >> 1;
    return min(qmin(x, y, p->l, l, m), qmin(x, y, p->r, m+1, r));
}

int qmax(int x, int y, node* p, int l = 1, int r = n) {
    if(x > r || l > y) return -INF;
    if(x <= l && r <= y) return p-> mx;
    int m = (l + r) >> 1;
    return max(qmax(x, y, p->l, l, m), qmax(x, y, p->r, m+1, r)); 
}

node *ver[N];
int ans[N];
const int sz = 448;
vector<iii> block[sz];

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) {
        scanf("%d %d %d", H+i, x+i, y+i);
        if(i + x[i] <= n) preadd[i+x[i]].emplace_back(i), predel[min(n, i+y[i]) + 1].emplace_back(i);
        if(i - x[i] >= 1) preadd[max(1, i-y[i])].emplace_back(i), predel[i-x[i] + 1].emplace_back(i);
    }
    ver[0] = ver[1] = build();
    for(int i = 1; i <= n; ++i) {
        for(int v : preadd[i]) ver[i] = update(v, true, ver[i]);//, cerr << "add -> " << i << ' ' << v << endl;
        for(int v : predel[i]) ver[i] = update(v, false, ver[i]);//, cerr << "del -> " << i << ' ' << v << endl;
        ver[i+1] = ver[i];
    }
    scanf("%d", &m);
    memset(ans, -1, sizeof ans);
    for(int i = 0, l, r; i < m; ++i) {
        scanf("%d %d", &l, &r); 
        block[l / sz].emplace_back(r, l, i);
    }
    for(int i = 0; i < sz; ++i) {
        sort(block[i].begin(), block[i].end());
        int pa = (i+1) * sz;
        int pmx = -1, ptr = pa;
        for(auto z : block[i]) {
            int l, r, idx; tie(r, l, idx) = z;
            // cerr << l << ' ' << r << endl;
            int imx = -1;
            while(ptr <= r) {
                pmx = max({pmx, H[ptr] - qmin(max(pa, ptr - y[ptr]), ptr - x[ptr], ver[ptr]), qmax(max(pa, ptr - y[ptr]), ptr - x[ptr], ver[ptr]) - H[ptr]});
                ptr++;
            }
            for(int i = min(r, pa-1); i >= l; --i) {
                imx = max({imx, H[i] - qmin(i+x[i], min(r, i+y[i]), ver[i]), qmax(i+x[i], min(r, i+y[i]), ver[i]) - H[i]});
            }
            ans[idx] = max(pmx, imx);
        }
    }
    for(int i = 0; i < m; ++i) printf("%d\n", ans[i]);
}

Compilation message

antennas.cpp: In function 'int main()':
antennas.cpp:57:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
antennas.cpp:59:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d", H+i, x+i, y+i);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:69:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &m);
     ~~~~~^~~~~~~~~~
antennas.cpp:72:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &l, &r); 
         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 13816 KB Output is correct
2 Correct 15 ms 13944 KB Output is correct
3 Correct 14 ms 13816 KB Output is correct
4 Correct 15 ms 13944 KB Output is correct
5 Correct 14 ms 13816 KB Output is correct
6 Correct 15 ms 13944 KB Output is correct
7 Correct 15 ms 13816 KB Output is correct
8 Correct 15 ms 13944 KB Output is correct
9 Correct 13 ms 13688 KB Output is correct
10 Correct 15 ms 13944 KB Output is correct
11 Correct 13 ms 13688 KB Output is correct
12 Correct 16 ms 13948 KB Output is correct
13 Correct 14 ms 13944 KB Output is correct
14 Correct 14 ms 13816 KB Output is correct
15 Correct 14 ms 14072 KB Output is correct
16 Correct 14 ms 13816 KB Output is correct
17 Correct 14 ms 13944 KB Output is correct
18 Correct 15 ms 13944 KB Output is correct
19 Correct 13 ms 13820 KB Output is correct
20 Correct 14 ms 13944 KB Output is correct
21 Correct 14 ms 13820 KB Output is correct
22 Correct 14 ms 13816 KB Output is correct
23 Correct 15 ms 13816 KB Output is correct
24 Correct 14 ms 13844 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 13816 KB Output is correct
2 Correct 15 ms 13944 KB Output is correct
3 Correct 14 ms 13816 KB Output is correct
4 Correct 15 ms 13944 KB Output is correct
5 Correct 14 ms 13816 KB Output is correct
6 Correct 15 ms 13944 KB Output is correct
7 Correct 15 ms 13816 KB Output is correct
8 Correct 15 ms 13944 KB Output is correct
9 Correct 13 ms 13688 KB Output is correct
10 Correct 15 ms 13944 KB Output is correct
11 Correct 13 ms 13688 KB Output is correct
12 Correct 16 ms 13948 KB Output is correct
13 Correct 14 ms 13944 KB Output is correct
14 Correct 14 ms 13816 KB Output is correct
15 Correct 14 ms 14072 KB Output is correct
16 Correct 14 ms 13816 KB Output is correct
17 Correct 14 ms 13944 KB Output is correct
18 Correct 15 ms 13944 KB Output is correct
19 Correct 13 ms 13820 KB Output is correct
20 Correct 14 ms 13944 KB Output is correct
21 Correct 14 ms 13820 KB Output is correct
22 Correct 14 ms 13816 KB Output is correct
23 Correct 15 ms 13816 KB Output is correct
24 Correct 14 ms 13844 KB Output is correct
25 Correct 1832 ms 17500 KB Output is correct
26 Correct 292 ms 15608 KB Output is correct
27 Execution timed out 3050 ms 17680 KB Time limit exceeded
28 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 923 ms 217960 KB Output is correct
2 Correct 1035 ms 242068 KB Output is correct
3 Correct 672 ms 169740 KB Output is correct
4 Correct 1028 ms 242160 KB Output is correct
5 Correct 425 ms 113364 KB Output is correct
6 Correct 1026 ms 241520 KB Output is correct
7 Correct 882 ms 209824 KB Output is correct
8 Correct 1061 ms 241992 KB Output is correct
9 Correct 129 ms 45004 KB Output is correct
10 Correct 1084 ms 242616 KB Output is correct
11 Correct 613 ms 151772 KB Output is correct
12 Correct 1067 ms 241960 KB Output is correct
13 Correct 741 ms 314096 KB Output is correct
14 Correct 681 ms 289228 KB Output is correct
15 Correct 613 ms 259576 KB Output is correct
16 Correct 635 ms 277744 KB Output is correct
17 Correct 782 ms 330604 KB Output is correct
18 Correct 663 ms 287500 KB Output is correct
19 Correct 699 ms 292856 KB Output is correct
20 Correct 660 ms 281656 KB Output is correct
21 Correct 657 ms 275840 KB Output is correct
22 Correct 672 ms 284060 KB Output is correct
23 Correct 708 ms 289012 KB Output is correct
24 Correct 619 ms 267304 KB Output is correct

Subtask #4
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 13816 KB Output is correct
2 Correct 15 ms 13944 KB Output is correct
3 Correct 14 ms 13816 KB Output is correct
4 Correct 15 ms 13944 KB Output is correct
5 Correct 14 ms 13816 KB Output is correct
6 Correct 15 ms 13944 KB Output is correct
7 Correct 15 ms 13816 KB Output is correct
8 Correct 15 ms 13944 KB Output is correct
9 Correct 13 ms 13688 KB Output is correct
10 Correct 15 ms 13944 KB Output is correct
11 Correct 13 ms 13688 KB Output is correct
12 Correct 16 ms 13948 KB Output is correct
13 Correct 14 ms 13944 KB Output is correct
14 Correct 14 ms 13816 KB Output is correct
15 Correct 14 ms 14072 KB Output is correct
16 Correct 14 ms 13816 KB Output is correct
17 Correct 14 ms 13944 KB Output is correct
18 Correct 15 ms 13944 KB Output is correct
19 Correct 13 ms 13820 KB Output is correct
20 Correct 14 ms 13944 KB Output is correct
21 Correct 14 ms 13820 KB Output is correct
22 Correct 14 ms 13816 KB Output is correct
23 Correct 15 ms 13816 KB Output is correct
24 Correct 14 ms 13844 KB Output is correct
25 Correct 1832 ms 17500 KB Output is correct
26 Correct 292 ms 15608 KB Output is correct
27 Execution timed out 3050 ms 17680 KB Time limit exceeded
28 Halted 0 ms 0 KB -