Submission #916783

#	Time	Username	Problem	Language	Result	Execution time	Memory
916783		sleepntsheep	Plahte (COCI17_plahte)	C++17	0 / 160	174 ms	68096 KiB

plahte

#include <iostream>
#include <map>
#include <fstream>
#include <iomanip>
#include <cmath>
#include <cassert>
#include <cstring>
#include <vector>
#include <algorithm>
#include <deque>
#include <set>
#include <utility>
#include <array>
#include <complex>

using u32 = unsigned;
using i32 = int;
using i64 = long long;
using u64 = unsigned long long;
using f64 = double;
using f80 = long double;

using namespace std;
using pt = complex<f80>;
#define ALL(x) begin(x), end(x)
#define ShinLena cin.tie(nullptr)->sync_with_stdio(false);
#define N 500005

int n, m;
array<int, 4> a[N];
array<int, 3> b[N];

vector<tuple<int, int, int>> ev_x;

map<tuple<int, int, int, int>, int> check;

void input_c()
{
    cin >> n >> m;
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < 4; ++j) cin >> a[i][j];
        if (check.count({a[i][0], a[i][1], a[i][2], a[i][3]})) assert(0);
        check[{a[i][0], a[i][1], a[i][2], a[i][3]}];
    }
    for (int i = 0; i < m; ++i) cin >> b[i][0] >> b[i][1] >> b[i][2];
}

int par[N], parball[N];

set<pair<int, int>> nfw;

void ins(int i)
{
    nfw.insert({a[i][3], i});
}

void del(int i)
{
    nfw.erase({a[i][3], i});
}

int qry(int down_brder, int up_brder)
{
    auto it = nfw.lower_bound({up_brder, -1});
    if (it != nfw.end() and a[it->second][1] <= down_brder) return it->second;
    return -1;
}


set<int> st[N];
basic_string<int> g[N];
int vis[N], ans[N];

void dfs(int u)
{
    if (vis[u]) return;
    vis[u] = 1;
    for (auto v : g[u])
    {
        dfs(v);
        if (st[v].size() > st[u].size()) st[v].swap(st[u]);
        for (auto x : st[v]) st[u].insert(x);
    }
    ans[u] = st[u].size();
}


int main()
{
    ShinLena;
    input_c();
    
    for (int i = 0; i < n; ++i)
    {
        ev_x.emplace_back(a[i][0], i, -3);
        ev_x.emplace_back(a[i][2], i, -1);
    }

    for (int i = 0; i < m; ++i)
    {
        ev_x.emplace_back(b[i][0], i, -2);
    }

    sort(ALL(ev_x));

    for (auto [x, id, ty] : ev_x)
    {
        if (ty == -1)
        {
            par[id] = qry(a[id][1] - 1, a[id][3] + 1);
            if (par[id] + 1) g[par[id]].push_back(id);
            del(id);
        }
        else if (ty == -3)
        {
            ins(id);
        }
        else
        {
            parball[id] = qry(b[id][1], b[id][1]);
            if (parball[id] != -1)
                st[parball[id]].insert(b[id][2]);
        }
    }

    for (int i = 0; i < n; ++i)
    {
        dfs(i);
        cout << ans[i] << '\n';
    }


    return 0;
}

• Subtask 1: 0 / 32
• Subtask 2: 0 / 32
• Subtask 3: 0 / 32
• Subtask 4: 0 / 32
• Subtask 5: 0 / 32