oj.uz

Submission #619892

# Submission time Handle Problem Language Result Execution time Memory
619892 2022-08-02T16:54:13 Z 2fat2code Plahte (COCI17_plahte) C++17
96 / 160
 375 ms 41808 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];
            }
        }
        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 115 ms 20480 KB Output is correct
2 Correct 119 ms 20560 KB Output is correct
3 Correct 6 ms 11516 KB Output is correct

Subtask #2
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 22920 KB Output is correct
2 Correct 129 ms 21084 KB Output is correct
3 Incorrect 7 ms 11520 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 224 ms 32204 KB Output is correct
2 Correct 211 ms 26260 KB Output is correct
3 Correct 6 ms 11476 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 375 ms 41808 KB Output is correct
2 Correct 357 ms 35836 KB Output is correct
3 Correct 6 ms 11604 KB Output is correct

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 375 ms 39380 KB Output is correct
2 Correct 353 ms 34840 KB Output is correct
3 Incorrect 6 ms 11604 KB Output isn't correct
4 Halted 0 ms 0 KB -