oj.uz

Submission #171181

# Submission time Handle Problem Language Result Execution time Memory
171181 2019-12-27T17:47:26 Z dolphingarlic Synchronization (JOI13_synchronization) C++14
30 / 100
 282 ms 16236 KB 
#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

struct Node {
    int range_l, range_r, info_l, info_r;

    Node operator+(Node b) {
        return {min(range_l, b.range_l), max(range_r, b.range_r), min(info_l, b.info_l), max(info_r, b.info_r)};
    }
};

int n, m, q;
bool active[100001];
vector<int> graph[100001];
Node segtree[400001], lazy[400001];

void push_lazy(int node, int l, int r) {
    if (!lazy[node].range_l) return;
    if (l == r) segtree[node] = lazy[node];
    else lazy[node * 2] = lazy[node * 2 + 1] = lazy[node];
    lazy[node] = {0, 0, 0, 0};
}

void build(int node = 1, int l = 1, int r = n) {
    if (l == r) segtree[node] = {l, l, l, l};
    else {
        int mid = (l + r) / 2;
        build(node * 2, l, mid);
        build(node * 2 + 1, mid + 1, r);
    }
}

void update(Node newval, int node = 1, int l = 1, int r = n) {
    push_lazy(node, l, r);
    if (l > newval.range_r || r < newval.range_l) return;
    if (l >= newval.range_l && r <= newval.range_r) lazy[node] = newval;
    else {
        int mid = (l + r) / 2;
        update(newval, node * 2, l, mid);
        update(newval, node * 2 + 1, mid + 1, r);
    }
}

Node query(int pos, int node = 1, int l = 1, int r = n) {
    push_lazy(node, l, r);
    if (l == r) return segtree[node];
    int mid = (l + r) / 2;
    if (pos > mid) return query(pos, node * 2 + 1, mid + 1, r);
    return query(pos, node * 2, l, mid);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> q;
    FOR(i, 1, n) {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    if (q == 1) {

    } else {
        build();
        while (m--) {
            int x;
            cin >> x;
            if (active[x]) {
                Node curr = query(x);
                Node l = curr, r = curr;
                l.range_r = x;
                r.range_l = x + 1;
                update(l);
                update(r);
            } else {
                Node newval = query(x) + query(x + 1);
                update(newval);
            }
            active[x] = !active[x];
        }

        while (q--) {
            int x;
            cin >> x;
            Node ans = query(x);
            cout << ans.info_r - ans.info_l + 1 << '\n';
        }
    }
    return 0;
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 20.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2808 KB Output is correct
3 Correct 4 ms 2680 KB Output is correct
4 Correct 4 ms 2808 KB Output is correct
5 Correct 4 ms 2680 KB Output is correct
6 Correct 5 ms 2808 KB Output is correct
7 Correct 22 ms 4216 KB Output is correct
8 Correct 242 ms 16072 KB Output is correct
9 Correct 244 ms 16120 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 282 ms 13648 KB Output is correct
2 Correct 203 ms 16120 KB Output is correct
3 Correct 147 ms 16236 KB Output is correct
4 Correct 165 ms 16008 KB Output is correct

Subtask #5
0 / 40.0

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