제출 #1301304

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1301304		codeac2215	Plahte (COCI17_plahte)	C++20	160 / 160	265 ms	76632 KiB

plahte

#include <bits/stdc++.h>
#define fi first
#define se second
#define xn '\n'
using namespace std ;

typedef long long ll ;
typedef pair <int, int> ii ;
typedef pair <ll, int> li;

const int Mod = 1e9 + 7 ;
const int N   = 1e5 ;
const ll MAX = 1e18;

int dy[] = { 0 , -1 , 0 , 1 } ;
int dx[] = { -1 , 0 , 1 , 0 } ;

struct hinh{
    int x1, y1, x2, y2;
};

struct diem{
    int x, y, color;
};

struct nen{
    int val, hinh, loai, id;
};

struct one{
    int y1, y2, id;
};

struct two{
    int y, color;
};

int n, m, comp_val;
int par[N + 22], ans[N + 22], st[N * 6 * 4 + 22], lazy[N * 6 * 4 + 22];

hinh cn[N + 22];
diem d[N + 22];
nen p[N * 6 + 22];

vector <one> be[N * 6 + 22], en[N * 6 + 22];
vector <two> node[N * 6 + 22];
set <int> set_cn[N + 22], pos;
vector <int> g[N + 22];

bool cmp_nen(nen x, nen y){
    return x.val < y.val;
}

bool cmp_cn(hinh a, hinh b){
    if (a.y1 == b.y1) return a.x1 > b.x1;
    return a.y1 > b.y1;
}

void compressed(){
    int sz = 0;
    for (int i = 1; i <= n; i++){
        p[++sz] = {cn[i].x1, 1, 1, i};
        p[++sz] = {cn[i].y1, 1, 2, i};
        p[++sz] = {cn[i].x2, 1, 3, i};
        p[++sz] = {cn[i].y2, 1, 4, i};
    }

    for (int i = 1; i <= m; i++){
        p[++sz] = {d[i].x, 2, 1, i};
        p[++sz] = {d[i].y, 2, 2, i};
    }

    sort(p + 1, p + sz + 1, cmp_nen);

    p[0].val = - 1;

    for (int i = 1; i <= sz; i++){
        if (p[i].val != p[i - 1].val) comp_val++;
        int tmp = p[i].hinh, dk = p[i].loai, id = p[i].id;

        if (tmp == 1){
            if (dk == 1) cn[id].x1 = comp_val;
            if (dk == 2) cn[id].y1 = comp_val;
            if (dk == 3) cn[id].x2 = comp_val;
            if (dk == 4) cn[id].y2 = comp_val;
        }

        if (tmp == 2){
            if (dk == 1) d[id].x = comp_val;
            if (dk == 2) d[id].y = comp_val;
        }
    }
}

void create(){
    for (int i = 1; i <= n; i++){
        be[cn[i].x1].push_back({cn[i].y1, cn[i].y2, i});
        en[cn[i].x2].push_back({cn[i].y1, cn[i].y2, i});
    }

    for (int i = 1; i <= m; i++){
        node[d[i].x].push_back({d[i].y, d[i].color});
    }
}

void down(int id){
    int val = lazy[id]; if (val == - 1) return ;

    st[id * 2] = val; lazy[id * 2] = val;
    st[id * 2 + 1] = val; lazy[id * 2 + 1] = val;

    lazy[id] = - 1;
}

void update(int id, int l, int r, int u, int v, int val){
    if (l > v || r < u) return ;

    if (u <= l && r <= v){
        st[id] = val;
        lazy[id] = 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);

    st[id] = max(st[id * 2], st[id * 2 + 1]);
}

int get(int id, int l, int r, int u, int v){
    if (l > v || r < u) return 0;

    if (u <= l && r <= v) return st[id];

    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));
}

void sweep_line(){
    memset(lazy, - 1, sizeof(lazy));

    for (int x = 1; x <= comp_val; x++){
        for (one td : be[x]){
            par[td.id] = get(1, 1, comp_val, td.y1, td.y2);
            update(1, 1, comp_val, td.y1, td.y2, td.id);
        }

        for (two td : node[x]){
            int id = get(1, 1, comp_val, td.y, td.y);
            if (id != 0) set_cn[id].insert(td.color);
        }

        for (one td : en[x]){
            update(1, 1, comp_val, td.y1, td.y2, par[td.id]);
        }
    }
}

void dfs(int u){
    for (int v : g[u]){
        dfs(v);

        if (u == 0) continue;

        if ( (int)set_cn[u].size() < (int) set_cn[v].size()) swap(set_cn[u], set_cn[v]);

        for (int x : set_cn[v]) set_cn[u].insert(x);

        set_cn[v].clear();
    }

    ans[u] = (int) set_cn[u].size();
}

void solution(){
    for (int i = 1; i <= n; i++){
        g[par[i]].push_back(i);
    }

    dfs(0);

    for (int i = 1; i <= n; i++){
        cout << ans[i] << xn;
    }
}

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

    cin >> n >> m;

    for (int i = 1; i <= n; i++){
        cin >> cn[i].x1 >> cn[i].y1 >> cn[i].x2 >> cn[i].y2;
    }

    for (int i = 1; i <= m; i++){
        cin >> d[i].x >> d[i].y >> d[i].color;
    }

    compressed();
    create();
    sweep_line();
    solution();

    return 0 ;
}

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