Submission #1208264

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208264		urejgi	Plahte (COCI17_plahte)	C++17	160 / 160	276 ms	26976 KiB

plahte

#pragma GCC optimize("O3,unroll-loops,fast-math")
#pragma GCC target("avx,avx2,bmi,bmi2,popcnt,lzcnt,tune=native,fma")
#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;

typedef long long ll;

struct S{
    int a,b,c,d,i;
};

signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int n,m; cin >> n >> m;
    vector<S> a; a.reserve(n);
    for(int i = 0; i < n; i++){
        S s;
        cin >> s.a >> s.b >> s.c >> s.d;
        s.i = i;
        a.push_back(s);
    }
    vector<int> p(n,-1);
    {
        vector<pair<int,int>> evs; evs.reserve(2*n);
        for(int i = 0; i < n; i++){
            evs.emplace_back(i, +1);
            evs.emplace_back(i, -1);
        }
        sort(evs.begin(),evs.end(),[&](auto l,auto r)->bool{
            if(l.f == r.f)
                return l.s > r.s;
            if(l.s == 1 && r.s == 1)
                return (a[l.f].a == a[r.f].a ? a[l.f].b < a[r.f].b : a[l.f].a < a[r.f].a);
            if(l.s == 1 && r.s == -1)
                return (a[l.f].a == a[r.f].c ? 1 : a[l.f].a < a[r.f].c);
            if(l.s == -1 && r.s == 1)
                return (a[l.f].c == a[r.f].a ? 0 : a[l.f].c < a[r.f].a);
            if(l.s == -1 && r.s == -1)
                return (a[l.f].c == a[r.f].c ? a[l.f].d > a[r.f].d : a[l.f].c < a[r.f].c);
        });
        set<array<int, 3>> s;
        for(auto[i,t]:evs){
            if(t < 0){
                s.erase(s.find({a[i].b, i, -1}));
                s.erase(s.find({a[i].d, i, +1}));
            }else{
                s.insert({a[i].b, i, -1});
                s.insert({a[i].d, i, +1});
                auto it = s.find({{a[i].b,i,-1}});
                if(it != s.begin()){
                    --it;
                    if((*it)[2] < 0) p[i] = (*it)[1];
                    else p[i] = p[(*it)[1]];
                }
            }
        }
    }
    vector<int> x(m), y(m), k(m);
    for(int i = 0; i < m; i++) cin >> x[i] >> y[i] >> k[i];
    vector<set<int>> have(n);
    {
        vector<pair<int,int>> evs; evs.reserve(2*n);
        for(int i = 0; i < n; i++){
            evs.emplace_back(i, +1);
            evs.emplace_back(i, -1);
        }
        for(int i = 0; i < m; i++){
            evs.emplace_back(i, 0);
        }
        sort(evs.begin(), evs.end(), [&](auto l, auto r) -> bool{
            if(l.s != 0 && r.s != 0){
                if(l.f == r.f) return l.s > r.s;
                if(l.s == 1 && r.s == 1)
                    return (a[l.f].a == a[r.f].a ? a[l.f].b < a[r.f].b : 
                        a[l.f].a < a[r.f].a);
                if(l.s == 1 && r.s == -1)
                    return (a[l.f].a == a[r.f].c ? 1 : a[l.f].a < a[r.f].c);
                if(l.s == -1 && r.s == 1)
                    return (a[l.f].c == a[r.f].a ? 0 : a[l.f].c < a[r.f].a);
                if(l.s == -1 && r.s == -1)
                    return (a[l.f].c == a[r.f].c ? a[l.f].d > a[r.f].d 
                        : a[l.f].c < a[r.f].c);
            }else{
                if(l.s != 0) return (l.s > 0 ? a[l.f].a <= x[r.f] : a[l.f].c < x[r.f]);
                if(r.s != 0) return (r.s > 0 ? x[l.f] < a[r.f].a : x[l.f] <= a[r.f].c);
                return x[l.f] < x[r.f];
            }
        });
        set<array<int, 3>> s;
        for(auto[i,t]:evs){
            if(t < 0){
                s.erase(s.find({a[i].b, i, -1}));
                s.erase(s.find({a[i].d, i, +1}));
            }else if(t == 0){
                auto it = s.lower_bound({y[i], -1, -1});
                if(it != s.end()){
                    if((*it)[2] > 0 || y[i] == a[(*it)[1]].b){
                        have[(*it)[1]].insert(k[i]);
                    }else{
                        if(p[(*it)[1]] >= 0){
                            have[p[(*it)[1]]].insert(k[i]);
                        }
                    }
                }
            }else{
                s.insert({a[i].b, i, -1});
                s.insert({a[i].d, i, +1});
            }
        }
    }
    vector<int> g[n];
    for(int i = 0; i < n; i++) if(p[i] >= 0) g[p[i]].push_back(i);
    vector<int> ans(n);
    function<void(int)> dfs = [&](int i) -> void{
        for(auto&j:g[i]){
            dfs(j);
            if(have[i].size() < have[j].size()) have[i].swap(have[j]);
            for(auto&x:have[j]) have[i].insert(x);
            have[j].clear();
        }
        ans[i] = have[i].size();
    };
    for(int i = 0; i < n; i++) if(p[i] < 0) dfs(i);
    for(auto&x:ans)cout<<x<<'\n';
    return 0;
}

Compilation message (stderr)

plahte.cpp: In lambda function:
plahte.cpp:42:9: warning: control reaches end of non-void function [-Wreturn-type]
   42 |         });
      |         ^
plahte.cpp: In lambda function:
plahte.cpp:90:9: warning: control reaches end of non-void function [-Wreturn-type]
   90 |         });
      |         ^

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