Submission #619862

#	Time	Username	Problem	Language	Result	Execution time	Memory
619862		2fat2code	Plahte (COCI17_plahte)	C++17	96 / 160	385 ms	46600 KiB

plahte

#include <bits/stdc++.h>
#define fr first
#define sc second
#define int long long
#define all(s) s.begin(), s.end()
#define rc(s) return cout << s, 0
using namespace std;

const int nmax = 160005;

int n, m, ans[nmax], par[nmax], sz[nmax], culori[nmax];
vector<int>nod[nmax];
set<int>seturi[nmax];

struct rect{
    pair<int,int> L, R;
    int indx, type;
    friend bool operator < (rect A, rect B){
        if(A.L.fr != B.L.fr){
            return A.L.fr < B.L.fr;
        }
        else if(A.R.sc != B.R.sc){
            return A.R.sc > B.R.sc;
        }
        else{
            return A.L.sc < B.L.sc;
        }
    }
};

multiset <pair<pair<int,int>,pair<int,int>>> O_o;

vector<rect>vecc;

void dfs(int s){
    sz[s] = 1;
    int curr = 0, marime = 0;
    for(auto it : nod[s]){
        dfs(it);
        sz[s] += sz[it];
        if(marime < sz[it]){
            marime = sz[it];
            curr = it;
        }
    }
    if(nod[s].size()){
        swap(seturi[s], seturi[curr]);
        for(auto it : nod[s]){
            if(it != curr){
                for(auto it1 : seturi[it]) seturi[s].insert(it1);
            }
        }
    }
    if(s > n && s <= n + m){
        seturi[s].insert(culori[s]);
    }
    if(s >= 1 && s <= n){
        ans[s] = seturi[s].size();
    }
}

int32_t main(){
    //ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
    //freopen("input.in", "r", stdin);
    cin >> n >> m;
    for(int i=1;i<=n;i++){
        rect AUX;
        cin >> AUX.L.fr >> AUX.L.sc >> AUX.R.fr >> AUX.R.sc;
        AUX.indx = i; AUX.type = 0;
        vecc.push_back(AUX);
    }
    for(int i=1;i<=m;i++){
        rect AUX;
        cin >> AUX.L.fr >> AUX.L.sc >> AUX.type;
        culori[i + n] = AUX.type;
        AUX.R.fr = AUX.L.fr;
        AUX.R.sc = AUX.L.sc;
        AUX.indx = n + i;
        vecc.push_back(AUX);
    }
    rect AUX;
    AUX.L.fr = AUX.L.sc = 0;
    AUX.R.fr = AUX.R.sc = 1e9;
    AUX.indx = n + m + 1;
    AUX.type = 0;
    vecc.push_back(AUX);
    sort(all(vecc));
    for(auto it : vecc){
        if(it.indx != n + m + 1){
            auto it1 = O_o.lower_bound({{it.R.sc, 0}, {0, 0}});
            while(it1->fr.sc < it.L.fr){
                auto it2 = it1; ++it1;
                O_o.erase(it2);
            }
            if(it1->sc.sc == 1 || it1->fr.fr == it.R.sc){
                par[it.indx] = it1->sc.fr;
            }
            else{
                par[it.indx] = par[it1->sc.fr];
            }
           // cout << "CHEEEECK " << it.indx << ' ' << it1->sc.fr << '\n';
        }
        O_o.insert({{it.L.sc, it.R.fr}, {it.indx, 0}});
        O_o.insert({{it.R.sc, it.R.fr}, {it.indx, 1}});
    }
    for(int i=1;i<=n+m;i++){
        nod[par[i]].push_back(i);
    }
    dfs(n + m + 1);
    for(int i=1;i<=n;i++){
        cout << ans[i] << '\n';
    }
}

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