oj.uz

답안 #796501

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
796501 2023-07-28T12:54:37 Z thimote75 Two Antennas (JOI19_antennas) C++14
24 / 100
 3000 ms 21228 KB 
#include <bits/stdc++.h>

using namespace std;

using idata = vector<int>;
using bdata = vector<bool>;

const int START = 0;
const int END   = 1;
const int QUERY = 2;

struct Event {
    int pos, type, id;

    Event (int pos, int type, int id) : pos(pos), type(type), id(id) {}

    bool operator< (const Event &other) const {
        if (pos == other.pos) return type < other.type;
        return pos < other.pos;
    }
};
using vEvent = vector<Event>;

struct SGData {
    bool enabled = false;
    int mx = -1; int mn = -1;

    void merge (SGData &left, SGData &right) {
        enabled = left.enabled | right.enabled;

        if (!left.enabled) {
            mx = right.mx;
            mn = right.mn;
        } else if (!right.enabled) {
            mx = left.mx;
            mn = left.mn;
        } else {
            mx = max(left.mx, right.mx);
            mn = min(left.mn, right.mn);
        }
    }
};

struct SegTree {
    vector<SGData> tree;

    int size, start, height;

    SegTree (idata heights) {
        size = heights.size();

        height = ceil(log2(size));
        start = 1 << height;

        tree.resize(start << 1);

        for (int i = 0; i < size; i ++) {
            tree[i + start].mx = heights[i];
            tree[i + start].mn = heights[i];
        }
    }
    void toggle (int index) {
        index += start;
        tree[index].enabled = !tree[index].enabled;

        index >>= 1;
        while (index != 0) {
            tree[index].merge(tree[index * 2], tree[index * 2 + 1]);

            index >>= 1;
        }
    }
    SGData query (int l, int r) {
        l += start;
        r += start;

        SGData local;
        SGData result;
        while (l < r) {
            if ((l & 1) == 1) { local.merge(result, tree[l]); result = local; }
            if ((r & 1) == 0) { local.merge(result, tree[r]); result = local; }
        
            l = (l + 1) >> 1;
            r = (r - 1) >> 1;
        }

        if (l == r) { local.merge(result, tree[l]); result = local; }

        return result;
    }
};

vEvent events;

idata heights;
idata left_q;
idata right_q;

bdata enabled;

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    cin >> N;

    heights.resize(N);
    left_q .resize(N);
    right_q.resize(N);
    for (int i = 0; i < N; i ++) {
        int h, a, b;
        cin >> h >> a >> b;

        heights[i] = h;
        left_q [i] = i + a;
        right_q[i] = i + b;

        events.push_back(Event( i - b,     START, i ));
        events.push_back(Event( i - a + 1, END,   i ));
        events.push_back(Event( i, QUERY, i ));
    }

    sort(events.begin(), events.end());

    int Q; cin >> Q;
    enabled.resize(N);

    SegTree tree(heights);

    for (int q = 0; q < Q; q ++) {
        int l, r;
        cin >> l >> r;
        l --; r --;

        int res = -1;
        for (Event &event : events) {
            if (event.type == START) {
                tree.toggle(event.id);
            } else if (event.type == END) {
                tree.toggle(event.id);
            } else {
                if (event.id < l) continue ;
                if (event.id > r) continue ;

                if (left_q[event.id] > r) continue ;
                SGData data = tree.query(left_q[event.id], min(r, right_q[event.id]));

                if (!data.enabled) continue ;
                res = max(res, data.mx - heights[event.id]);
                res = max(res, heights[event.id] - data.mn);
            }
        }

        cout << res << "\n";
    }
}

Subtask #1
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 320 KB Output is correct
2 Correct 5 ms 324 KB Output is correct
3 Correct 5 ms 340 KB Output is correct
4 Correct 7 ms 364 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 4 ms 324 KB Output is correct
7 Correct 7 ms 340 KB Output is correct
8 Correct 8 ms 324 KB Output is correct
9 Correct 3 ms 320 KB Output is correct
10 Correct 6 ms 324 KB Output is correct
11 Correct 2 ms 212 KB Output is correct
12 Correct 7 ms 340 KB Output is correct
13 Correct 3 ms 340 KB Output is correct
14 Correct 5 ms 340 KB Output is correct
15 Correct 3 ms 340 KB Output is correct
16 Correct 5 ms 356 KB Output is correct
17 Correct 4 ms 340 KB Output is correct
18 Correct 5 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 5 ms 340 KB Output is correct
21 Correct 5 ms 320 KB Output is correct
22 Correct 6 ms 340 KB Output is correct
23 Correct 4 ms 320 KB Output is correct
24 Correct 5 ms 340 KB Output is correct

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 320 KB Output is correct
2 Correct 5 ms 324 KB Output is correct
3 Correct 5 ms 340 KB Output is correct
4 Correct 7 ms 364 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 4 ms 324 KB Output is correct
7 Correct 7 ms 340 KB Output is correct
8 Correct 8 ms 324 KB Output is correct
9 Correct 3 ms 320 KB Output is correct
10 Correct 6 ms 324 KB Output is correct
11 Correct 2 ms 212 KB Output is correct
12 Correct 7 ms 340 KB Output is correct
13 Correct 3 ms 340 KB Output is correct
14 Correct 5 ms 340 KB Output is correct
15 Correct 3 ms 340 KB Output is correct
16 Correct 5 ms 356 KB Output is correct
17 Correct 4 ms 340 KB Output is correct
18 Correct 5 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 5 ms 340 KB Output is correct
21 Correct 5 ms 320 KB Output is correct
22 Correct 6 ms 340 KB Output is correct
23 Correct 4 ms 320 KB Output is correct
24 Correct 5 ms 340 KB Output is correct
25 Execution timed out 3057 ms 1100 KB Time limit exceeded
26 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 144 ms 19620 KB Output is correct
2 Correct 148 ms 21220 KB Output is correct
3 Correct 102 ms 16784 KB Output is correct
4 Correct 147 ms 21152 KB Output is correct
5 Correct 71 ms 10224 KB Output is correct
6 Correct 148 ms 21228 KB Output is correct
7 Correct 131 ms 19248 KB Output is correct
8 Correct 148 ms 21224 KB Output is correct
9 Correct 21 ms 3312 KB Output is correct
10 Correct 149 ms 21228 KB Output is correct
11 Correct 98 ms 12568 KB Output is correct
12 Correct 149 ms 21176 KB Output is correct
13 Correct 118 ms 21100 KB Output is correct
14 Correct 123 ms 21072 KB Output is correct
15 Correct 117 ms 21108 KB Output is correct
16 Correct 119 ms 21112 KB Output is correct
17 Correct 120 ms 21024 KB Output is correct
18 Correct 121 ms 21124 KB Output is correct
19 Correct 119 ms 21148 KB Output is correct
20 Correct 124 ms 21152 KB Output is correct
21 Correct 120 ms 21076 KB Output is correct
22 Correct 123 ms 21116 KB Output is correct
23 Correct 119 ms 21116 KB Output is correct
24 Correct 139 ms 21116 KB Output is correct

Subtask #4
0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 320 KB Output is correct
2 Correct 5 ms 324 KB Output is correct
3 Correct 5 ms 340 KB Output is correct
4 Correct 7 ms 364 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 4 ms 324 KB Output is correct
7 Correct 7 ms 340 KB Output is correct
8 Correct 8 ms 324 KB Output is correct
9 Correct 3 ms 320 KB Output is correct
10 Correct 6 ms 324 KB Output is correct
11 Correct 2 ms 212 KB Output is correct
12 Correct 7 ms 340 KB Output is correct
13 Correct 3 ms 340 KB Output is correct
14 Correct 5 ms 340 KB Output is correct
15 Correct 3 ms 340 KB Output is correct
16 Correct 5 ms 356 KB Output is correct
17 Correct 4 ms 340 KB Output is correct
18 Correct 5 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 5 ms 340 KB Output is correct
21 Correct 5 ms 320 KB Output is correct
22 Correct 6 ms 340 KB Output is correct
23 Correct 4 ms 320 KB Output is correct
24 Correct 5 ms 340 KB Output is correct
25 Execution timed out 3057 ms 1100 KB Time limit exceeded
26 Halted 0 ms 0 KB -