Submission #404720

#	Time	Username	Problem	Language	Result	Execution time	Memory
404720		jeroenodb	Plahte (COCI17_plahte)	C++14	0 / 160	345 ms	22412 KiB

plahte

#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x),end(x)
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; }
#define debug(a) cerr << "(" << #a << ": " << a << ")\n";
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
#ifndef LOCAL
const int mxN = 1e5+1, oo = 1e9, ptwo = 1<<17;
#else
const int mxN = 1e3+1, oo = 1e9, ptwo = 1<<8;
#endif
unordered_set<int> colours[mxN];
int ans[mxN];
vi kid[mxN];
bitset<mxN> notroot;

void dfs(int at) {
    for(int to:kid[at]) {
        dfs(to);
        if(colours[to].size()>colours[at].size()) {
            swap(colours[at],colours[to]);
        }
        for(auto c: colours[to]) colours[at].insert(c);
    }
    ans[at] = colours[at].size();
}


struct event {
    int x,y1,y2,i;
    bool end = false, sheet=true;
    event() {}
    event(int _x,int Y1, int Y2, int I, bool End) : x(_x),y1(Y1),y2(Y2),i(I), end(End) {
    }
    bool operator<(const event& o) const {
        if(x==o.x) {
            if(sheet==o.sheet) return false;
            else if(sheet) return !end;
            else return o.end;
        }
        return x<o.x;
    }
};
vector<event> es;
struct segment {
    int y1,y2,i;
    bool operator<(const segment& o) const {
        return y2 < o.y2;
    }
};
int main() {
    int n,m; cin >> n >> m;
    es.resize(2*n+m);
    for(int i=0;i<n;++i) {
        auto& e1 = es[2*i],&e2 = es[2*i+1];
        int a,b,c,d; cin >> a >> b >> c >> d;
        e1 = event(a,b,d,i,false);
        e2 = event(c,b,d,i,true);
    }
    for(int i=2*n;i<2*n+m;++i) {
        auto& b = es[i];
        cin >> b.x >> b.y1 >> b.i;
        b.sheet = false;
    }
    sort(all(es));
    int level = 0;

    set<segment> s;
    for(auto& e : es) {
        auto getsheet = [&]() {
            auto iter = s.lower_bound({e.y1,e.y1,e.i});
            if(iter==s.end()) return -1;
            if(iter->y1>e.y1) return -1;
            return iter->i;
        };
        if(e.sheet) {
            if(e.end) {
                s.erase({e.y1,e.y2,e.i});
            } else {
                int par = getsheet();
                if(par!=-1){
                    kid[par].push_back(e.i);
                    notroot[e.i] = true;
                } 
                s.insert({e.y1,e.y2,e.i});
            }
        } else {
            // shoot paintball
            int target = getsheet();
            if(target!=-1) 
                colours[target].insert(e.i);
        }
        level++;
    }
    for(int i=0;i<n;++i) {
        if(!notroot[i]) dfs(i);
    }
    for(int i=0;i<n;++i) {
        cout << ans[i] << '\n';
    }
}

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