Submission #1279585

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279585		LmaoLmao	Plahte (COCI17_plahte)	C++20	0 / 160	1326 ms	32784 KiB

plahte

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define name "a"
using namespace std;

using ii = pair<int,int>;
using aa5 = array<int,5>;
const int N = 1e5+5;

vector<int> adj[N];
aa5 a[N],b[N];
set<int> s;

int inside(aa5 a,aa5 b) {
    if(a[0] < b[0] && a[1] < b[1] && a[2]>b[2] && a[3]>b[3] ) {
        return 1;
    }
    return 0;
}

void build(int u) {
    for(int x:s) {
        build(x);
        if(inside(a[u],a[x])) {
            adj[u].push_back(x);
        }
    }
}

vector<int> nen;

vector<int> del[N*4];
int getpos(int x) {
    return lower_bound(nen.begin(),nen.end(),x)-nen.begin()+1;
}

int ans[N];
set<int> color[N];

void dfs(int u) {
    for(int v:adj[u]) {
        dfs(v);
        if(color[v].size()>color[u].size()) swap(color[u],color[v]);
        for(int x:color[v]) {
            color[u].insert(x);
        }
    }
    //cout << u << ' ' << color[u].size() << ' ' << endl;
    ans[u]=color[u].size();
    return;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,m;
    cin >> n >> m;
    for(int i=1;i<=n;i++) {
        cin >> a[i][0] >> a[i][1] >> a[i][2] >> a[i][3];
        a[i][4]=i;
        nen.push_back(a[i][0]);
        nen.push_back(a[i][2]);
        s.insert(i);
    }
    sort(a+1,a+1+n);
    for(int i=n;i>0;i--) {
        auto it=s.upper_bound(i);
        while(it!=s.end() && a[*it][0]<=a[i][2]) {
            if(inside(a[i],a[*it])) {
                adj[a[i][4]].push_back(a[*it][4]);
                it=s.erase(it);
            }
            else ++it;
        }
    }
    for(int i=1;i<=m;i++) {
        cin >> b[i][0] >> b[i][1] >> b[i][2];
        b[i][3]=i;
        nen.push_back(a[i][0]);
        nen.push_back(a[i][2]);
    }
    sort(b+1,b+1+m);
    sort(nen.begin(),nen.end());
    set<ii> reg;
    int j=1;
    for(int i=1;i<=m;i++) {
        while(j<=n && a[j][0]<=b[i][0]) {
            reg.insert({a[j][3],a[j][4]});
            int t=upper_bound(b+1,b+1+n,aa5{a[j][2],-1,-1,-1,-1})-b;
            del[t].push_back(j);
            j++;
        }
        for(int x:del[i]) {
            reg.erase({a[x][3],a[x][4]});
        }
        auto it = reg.lower_bound({b[i][1],0});
        if(it!=reg.end()) {
            color[(*it).se].insert(b[i][2]);
            //cout << b[i][2] << ' ' << (*it).se << endl;
        }
        //cout << reg.size() << endl;
    }
    for(int x:s) {
        dfs(x);
    }
    for(int i=1;i<=n;i++) {
        cout << ans[i] << endl;
    }
    return 0;
}

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