Submission #1078625

#	Time	Username	Problem	Language	Result	Execution time	Memory
1078625		HiepVu217	Plahte (COCI17_plahte)	C++17	0 / 160	192 ms	80720 KiB

plahte

#include <bits/stdc++.h>
using namespace std;
const int N = 4e5 + 17;
int n, m, sz, b[N];
int st[N], lz[N];
int pre[N], ans[N], z[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] < 0)
        {
            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);
            if (!pre[id])
            {
                update (1, 1, sz, l, r, id);
                continue;
            }
            if (pre[id] < id)
            {
                update (1, 1, sz, l, r, id);
                adj[pre[id]].push_back(id);
                continue;
            }
            z[id] = pre[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;
    }
    memset (ans, -1, sizeof(ans));
    for (int i = 1; i <= n; ++i)
    {
        if (ans[i] < 0)
        {
            dfs (i, 0);
        }
    }
    for (int i = 1; i <= n; ++i)
    {
        if (z[i])
        {
            ans[i] = ans[z[i]];
        }
    }
    for (int i = 1; i <= n; ++i)
    {
        cout << ans[i] << "\n";
    }
}

Compilation message (stderr)

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: 0 / 32
• Subtask 2: 0 / 32
• Subtask 3: 0 / 32
• Subtask 4: 0 / 32
• Subtask 5: 0 / 32