Submission #82705

#	Time	Username	Problem	Language	Result	Execution time	Memory
82705		Milki	Plahte (COCI17_plahte)	C++14	0 / 160	255 ms	24736 KiB

plahte

#include <bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define _ << " " <<
#define sz(x) (int)x.size()
#define pb(x) push_back(x)

typedef long long ll;
typedef pair<int, int> point;

const int MAXN = 8e4 + 5, INF = 1e9;

struct event{
    int x, y1, y2, tip, id;

    friend bool operator < (const event A, const event B){
        if(A.x != B.x) return A.x < B.x;
        if(A.y1 != B.y1) return A.y1 < B.y1;
        return A.tip < B.tip;
    }
};

int n, m;
event rectangles[MAXN];
vector <event> rectangle, v;
int par[MAXN];
vector <int> colors[MAXN], E[MAXN];

void load(){
    ios_base::sync_with_stdio(false); cin.tie(0);

    cin >> n >> m;
    REP(i, n){
        event a, b;
        cin >> a.x >> a.y1 >> b.x >> b.y2;
        a.y2 = b.y2; b.y1 = a.y1;
        a.tip = -1; b.tip = 1;
        a.id = b.id = i;
        swap(b.y1, b.y2);
        v.pb(a); v.pb(b);
        rectangles[i] = a;
    }
    REP(i, m){
        event a;
        cin >> a.x >> a.y1 >> a.id;
        a.tip = 0;
        v.pb(a);
    }
}

void sweep(){
    sort(v.begin(), v.end());
    set<point> S;
    S.insert(point(-1, -1));

    for(auto it : v){
        //cout << "tip " _ it.tip _ it.x _ it.y1 _ it.y2 _ "\n";
        if(it.tip == -1){
            auto pos = S.lower_bound(point(it.y1, -INF)); pos --;
            point val = *pos;

            if(val.first != -1 && rectangles[val.second].y2 > it.y2 && rectangles[val.second].y1 < it.y1){
                par[it.id] = val.second;
                E[val.second].pb(it.id);
            }
            else{
                if(val.first != -1){
                    val.second = par[val.second];
                    if(val.second != -1 && rectangles[val.second].y2 > it.y2 && rectangles[val.second].y1 < it.y1){
                        par[it.id] = val.second;
                        E[val.second].pb(it.id);
                    }
                    else
                        par[it.id] = -1;
                }
                else
                    par[it.id] = -1;
            }
            S.insert(point(it.y1, it.id));
            S.insert(point(it.y2, it.id));
        }
        else if(it.tip == 0){
            auto pos = S.lower_bound(point(it.y1, -INF));
            if(pos != S.end()){
                point val = *pos;
                if(val.first != -1 && rectangles[val.second].y1 <= it.y1)
                    colors[val.second].pb(it.id);
                else if(val.first != -1){
                    val.second = par[val.second];
                    if(val.second != -1 && rectangles[val.second].y1 <= it.y1 && rectangles[val.second].y2 >= it.y1)
                        colors[val.second].pb(it.id);
                }
            }
            pos --; point val = *pos;
            if(val.first != -1 && rectangles[val.second].y2 >= it.y1)
                colors[val.second].pb(it.id);
            else if(val.first != -1){
                val.second = par[val.second];
                if(val.second != -1 && rectangles[val.second].y1 <= it.y1 && rectangles[val.second].y2 >= it.y1)
                    colors[val.second].pb(it.id);
            }
        }
        else{
            S.erase(point(it.y1, it.id));
            S.erase(point(it.y2, it.id));
        }
    }
    /*REP(i, n){
        for(auto it : colors[i])
            cout <<it << " ";
        cout << "\n";
    } */
}

int sz[MAXN];

void dfsSz(int x, int p){
    sz[x] = 1;
    for(auto it : E[x]){
        if(it == p) continue;
        dfsSz(it, x);
        sz[x] += sz[it];
    }
}

bool heavy[MAXN];
int cnt, have[MAXN], sol[MAXN];

void add(int x, int p, int val){
    for(auto it : colors[x]){
        have[it] += val;
        if(val == 1 && have[it] == 1) cnt ++;
        else if(val == -1 && have[it] == 0) cnt --;
    }

    for(auto it : E[x]){
        if(it == p || heavy[it]) continue;
        add(it, x, val);
    }
}

void dfs(int x, int p, bool isHeavy = false){
    int mx = -1, mx_id = -1;
    for(auto it : E[x]){
        if(it == p) continue;
        if(sz[it] > mx){
            mx = sz[it];
            mx_id = it;
        }
    }

    for(auto it : E[x]){
        if(it == p || it == mx_id) continue;
        dfs(it, x);
    }

    if(mx != -1){
        dfs(mx_id, x, true);
        heavy[mx_id] = true;
    }
    add(x, p, 1);
    sol[x] = cnt;
    //cout << cnt _ x _ SOL[x] << " ZASTO\n";

    if(mx != -1)
        heavy[mx_id] = false;
    if(!isHeavy){
        add(x, p, -1);
    }
}

int main(){
    load();
    sweep();
    REP(i, n)
        if(par[i] == -1){
            dfsSz(i, par[i]);
            dfs(i, par[i]);
        }
    REP(i, n)
        cout << sol[i] << "\n";
}

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