oj.uz

Submission #619894

# Submission time Handle Problem Language Result Execution time Memory
619894 2022-08-02T16:55:24 Z 2fat2code Plahte (COCI17_plahte) C++17
160 / 160
 458 ms 42332 KB 
#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];
            }
        }
        if(it.type  == 0){
            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);
    assert(sz[n + m + 1] == n + m + 1);
    for(int i=1;i<=n;i++){
        cout << ans[i] << '\n';
    }
}

Subtask #1
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 21032 KB Output is correct
2 Correct 113 ms 21088 KB Output is correct
3 Correct 7 ms 11604 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 23532 KB Output is correct
2 Correct 123 ms 21624 KB Output is correct
3 Correct 6 ms 11604 KB Output is correct

Subtask #3
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 226 ms 32748 KB Output is correct
2 Correct 215 ms 26912 KB Output is correct
3 Correct 6 ms 11576 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 360 ms 42332 KB Output is correct
2 Correct 369 ms 36400 KB Output is correct
3 Correct 8 ms 11604 KB Output is correct

Subtask #5
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 458 ms 39928 KB Output is correct
2 Correct 354 ms 35448 KB Output is correct
3 Correct 9 ms 11684 KB Output is correct