oj.uz

Submission #1078632

# Submission time Handle Problem Language Result Execution time Memory
1078632 2024-08-28T01:42:14 Z vjudge1 Plahte (COCI17_plahte) C++17
160 / 160
 281 ms 51812 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 4e5 + 17;
int n, m, sz, b[N];
int st[4 * N], lz[4 * N];
int pre[N], ans[N];
vector <int> adj[N];
map <int, bool> c[N];
struct rect
{
    int x, l, r, t, id;
} a[N];
bool cmp (rect x, rect y)
{
    if (x.x != y.x)
    {
        return x.x < y.x;
    }
    return x.t > y.t;
}
void build (int id, int l, int r)
{
    lz[id] = -1;
    if (l == r)
    {
        return;
    }
    int mid = l + r >> 1;
    build (id * 2, l, mid);
    build (id * 2 + 1, mid + 1, r);
}
void down (int id)
{
    if (lz[id] < 0)
    {
        return;
    }
    st[id * 2] = lz[id];
    st[id * 2 + 1] = lz[id];
    lz[id * 2] = lz[id];
    lz[id * 2 + 1] = lz[id];
    lz[id] = -1;
}
void update (int id, int l, int r, int u, int v, int z)
{
    if (u > r || l > v)
    {
        return;
    }
    if (u <= l && v >= r)
    {
        st[id] = lz[id] = z;
        return;
    }
    int mid = l + r >> 1;
    down(id);
    update (id * 2, l, mid, u, v, z);
    update (id * 2 + 1, mid + 1, r, u, v, z);
    st[id] = max (st[id * 2], st[id * 2 + 1]);
}
int get (int id, int l, int r, int u, int v)
{
    if (u > r || l > v)
    {
        return 0;
    }
    if (u <= l && v >= r)
    {
        return st[id];
    }
    int mid = l + r >> 1;
    down(id);
    return max (get (id * 2, l, mid, u, v), get (id * 2 + 1, mid + 1, r, u, v));
}
void dfs (int u, int pr)
{
    for (int v: adj[u])
    {
        if (v == pr)
        {
            continue;
        }
        if (!ans[v])
        {
            dfs (v, u);
        }
        if (c[v].size() > c[u].size())
        {
            swap (c[u], c[v]);
        }
        for (auto [x, s]: c[v])
        {
            c[u][x] = 1;
        }
    }
    ans[u] = c[u].size();
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for (int i = 1, u, v, x, y; i <= n; ++i)
    {
        cin >> u >> v >> x >> y;
        a[++sz] = {u, v, y, 1, i};
        b[sz] = v;
        a[++sz] = {x, v, y, -1, i};
        b[sz] = y;
    }
    for (int i = 1, x, y, k; i <= m; ++i)
    {
        cin >> x >> y >> k;
        a[++sz] = {x, y, y, 0, k};
        b[sz] = y;
    }
    sort (a + 1, a + sz + 1, cmp);
    sort (b + 1, b + sz + 1);
    build (1, 1, sz);
    for (int i = 1; i <= sz; ++i)
    {
        auto [x, l, r, t, id] = a[i];
        l = lower_bound (b + 1, b + sz + 1, l) - b;
        r = lower_bound (b + 1, b + sz + 1, r) - b;
        if (t > 0)
        {
            pre[id] = get (1, 1, sz, l, r);
            update (1, 1, sz, l, r, id);
            if (!pre[id])
            {
                continue;
            }
            adj[pre[id]].push_back(id);
            continue;
        }
        if (t < 0)
        {
            update (1, 1, sz, l, r, pre[id]);
            continue;
        }
        int z = get (1, 1, sz, l, r);
        c[z][id] = 1;
    }
    for (int i = 1; i <= n; ++i)
    {
        if (!ans[i])
        {
            dfs (i, 0);
        }
        cout << ans[i] << "\n";
    }
}

Compilation message

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

Subtask #1
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 35664 KB Output is correct
2 Correct 85 ms 36176 KB Output is correct
3 Correct 13 ms 28560 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 36944 KB Output is correct
2 Correct 102 ms 35864 KB Output is correct
3 Correct 13 ms 28504 KB Output is correct

Subtask #3
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 43348 KB Output is correct
2 Correct 165 ms 40784 KB Output is correct
3 Correct 16 ms 28508 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 273 ms 51812 KB Output is correct
2 Correct 269 ms 47184 KB Output is correct
3 Correct 13 ms 28508 KB Output is correct

Subtask #5
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 259 ms 50112 KB Output is correct
2 Correct 281 ms 46516 KB Output is correct
3 Correct 13 ms 28508 KB Output is correct