oj.uz

Submission #491744

# Submission time Handle Problem Language Result Execution time Memory
491744 2021-12-04T08:52:24 Z hoanghq2004 Plahte (COCI17_plahte) C++14
160 / 160
 327 ms 39776 KB 
#include <bits/stdc++.h>

using namespace std;

const int maxval = 1e6 + 10;

int n, m;
int par[100010];
vector <int> adj[100010];
set <int> s[100010];
struct node {
    int val, lazy;
} st[4 * maxval];;

void down(int id) {
    if (st[id].lazy == -1) return;
    st[id * 2].lazy = st[id].lazy;
    st[id * 2 + 1].lazy = st[id].lazy;
    st[id * 2].val = st[id].lazy;
    st[id * 2 + 1].val = st[id].lazy;
    st[id].lazy = -1;
}

void update(int id, int l, int r, int u, int v, int val) {
    if (u > r || l > v) return;
    if (u <= l && r <= v) {
        st[id].val = val;
        st[id].lazy = val;
        return;
    }
    down(id);
    int mid = l + r >> 1;
    update(id * 2, l, mid, u, v, val);
    update(id * 2 + 1, mid + 1, r, u, v, val);
}

int get(int id, int l, int r, int u, int v) {
    if (u > r || l > v) return -1;
    if (u <= l && r <= v) return st[id].val;
    down(id);
    int mid = l + r >> 1;
    return max(get(id * 2, l, mid, u, v), get(id * 2 + 1, mid + 1, r, u, v));
}

struct events {
    int x, l, r, c, cl;
    int operator < (const events& other) const {
        return (x < other.x || (x == other.x && c > other.c));
    }
};

vector <events> e;
int cnt[100010];

void dfs(int u) {
    for (auto v: adj[u]) {
        dfs(v);
        if (s[u].size() < s[v].size()) s[u].swap(s[v]);
        for (auto x: s[v]) s[u].insert(x);
        s[v].clear();
    }
    cnt[u] = s[u].size();
}

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

    vector <int> data;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        e.push_back({a, b, d, 1, i});
        e.push_back({c, b, d, -1, i});
        data.push_back(b);
        data.push_back(d);
    }

    for (int i = 1; i <= m; ++i) {
        int x, y, c;
        cin >> x >> y >> c;
        e.push_back({x, y, y, 0, c});
        data.push_back(y);
    }
    sort(data.begin(), data.end());
    for (int i = 1; i <= maxval; ++i)
        st[i].lazy = -1;
    sort(e.begin(), e.end());
    for (auto p: e) {
        if (p.c == 1) {
            int L = lower_bound(data.begin(), data.end(), p.l) - data.begin() + 1;
            int R = lower_bound(data.begin(), data.end(), p.r) - data.begin() + 1;
            par[p.cl] = get(1, 1, maxval, L, R);
            update(1, 1, maxval, L, R, p.cl);
            adj[par[p.cl]].push_back(p.cl);
        }
        if (p.c == -1) {
            int L = lower_bound(data.begin(), data.end(), p.l) - data.begin() + 1;
            int R = lower_bound(data.begin(), data.end(), p.r) - data.begin() + 1;
            update(1, 1, maxval, L, R, par[p.cl]);
        }
        if (p.c == 0) {
            int L = lower_bound(data.begin(), data.end(), p.l) - data.begin() + 1;
            int R = lower_bound(data.begin(), data.end(), p.r) - data.begin() + 1;
            int id = get(1, 1, maxval, L, R);
            s[id].insert(p.cl);
        }
    }
    dfs(0);
    for (int i = 1; i <= n; ++i) cout << cnt[i] << "\n";
}

Compilation message

plahte.cpp: In function 'void update(int, int, int, int, int, int)':
plahte.cpp:32:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   32 |     int mid = l + r >> 1;
      |               ~~^~~
plahte.cpp: In function 'int get(int, int, int, int, int)':
plahte.cpp:41:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   41 |     int mid = l + r >> 1;
      |               ~~^~~

Subtask #1
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 20848 KB Output is correct
2 Correct 96 ms 20736 KB Output is correct
3 Correct 11 ms 15160 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 23496 KB Output is correct
2 Correct 103 ms 22108 KB Output is correct
3 Correct 7 ms 15180 KB Output is correct

Subtask #3
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 30412 KB Output is correct
2 Correct 192 ms 26320 KB Output is correct
3 Correct 10 ms 15124 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 327 ms 39776 KB Output is correct
2 Correct 311 ms 32532 KB Output is correct
3 Correct 8 ms 15180 KB Output is correct

Subtask #5
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 309 ms 37336 KB Output is correct
2 Correct 287 ms 32428 KB Output is correct
3 Correct 8 ms 15180 KB Output is correct