Submission #234569

#	Time	Username	Problem	Language	Result	Execution time	Memory
234569		VEGAnn	Plahte (COCI17_plahte)	C++14	0 / 160	985 ms	208824 KiB

plahte

#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define sz(x) ((int)x.size())
#define a2 array<int,2>
#define a3 array<int,3>
#define PB push_back
using namespace std;
typedef long long ll;
const int N = 200100;
const int PW = 20;
const int oo = 2e9;
unordered_map<int, vector<int> > ver;
vector<int> vf, cols[N], g[N];
int a[N], b[N], c[N], d[N], n, m, nm[N], id, pre[N], tin[N], tout[N], tt = 0, up[N][PW];
int ans[N], ad[N], del[N];

bool cmp(int _x, int _y){
    return a[_x] < a[_y];
}

bool cmp1(int _x, int _y){
    return tin[_x] < tin[_y];
}

struct seg_tree{
    vector<int> elements;
    vector<a2> mn;

    seg_tree(): elements(0), mn(0) {}

    void real_build(){
        sort(all(elements));
        elements.resize(unique(all(elements)) - elements.begin());

        mn.resize(sz(elements) * 4 + 10);

        for (int it = 1; it < sz(mn); it++)
            mn[it] = {-oo, oo};
    }

    void real_search(int v, int l, int r, int vlt){
        if (l == r){
            id = mn[v][1];
            return;
        }

        int md = (l + r) >> 1;

        if (mn[v + v + 1][0] >= vlt)
            real_search(v + v + 1, md + 1, r, vlt);
        else real_search(v + v, l, md, vlt);
    }

    void search(int v, int l, int r, int vls, int vlt){
        if (elements[l] > vls || id >= 0) return;

        if (elements[r] <= vls){
            if (mn[v][0] >= vlt)
                real_search(v, l, r, vlt);
            return;
        }

        int md = (l + r) >> 1;

        search(v + v + 1, md + 1, r, vls, vlt);
        search(v + v, l, md, vls, vlt);
    }

    void update(int v, int l, int r, int vls, int vlt){
        if (l == r){
            mn[v] = {vlt, id};
            return;
        }

        int md = (l + r) >> 1;

        if (elements[md] >= vls)
            update(v + v, l, md, vls, vlt);
        else update(v + v + 1, md + 1, r, vls, vlt);

        mn[v] = max(mn[v + v], mn[v + v + 1]);
    }
};

seg_tree st[4 * N];

void build(int v, int l, int r, int vlf, int vls){
    st[v].elements.PB(vls);

    if (l == r) return;

    int md = (l + r) >> 1;

    if (vlf <= vf[md])
        build(v + v, l, md, vlf, vls);
    else build(v + v + 1, md + 1, r, vlf, vls);
}

void real_build(int v, int l, int r){
    st[v].real_build();

    if (l == r) return;

    int md = (l + r) >> 1;

    real_build(v + v, l, md);
    real_build(v + v + 1, md + 1, r);
}

void search(int v, int l, int r, int vlf, int vls, int vlt){
    if (vlf > vf[r] || id >= 0) return;

    if (vlf <= vf[l]){
        st[v].search(1, 0, sz(st[v].elements) - 1, vls, vlt);
        return;
    }

    int md = (l + r) >> 1;

    search(v + v, l, md, vlf, vls, vlt);
    search(v + v + 1, md + 1, r, vlf, vls, vlt);
}

void update(int v, int l, int r, int vlf, int vls, int vlt){
    st[v].update(1, 0, sz(st[v].elements) - 1, vls, vlt);
    if (l == r) return;

    int md = (l + r) >> 1;

    if (vf[md] >= vlf)
        update(v + v, l, md, vlf, vls, vlt);
    else update(v + v + 1, md + 1, r, vlf, vls, vlt);
}

void dfs(int v){
    tin[v] = ++tt;

    if (v != 0) {
        for (int po = 1; po < PW; po++)
            up[v][po] = up[up[v][po - 1]][po - 1];
    }

    for (int u : g[v])
        dfs(u);

    tout[v] = ++tt;
}

bool upper(int a, int b){
    return (tin[a] <= tin[b] && tout[a] >= tout[b]);
}

int lca(int a, int b){
    if (upper(a, b)) return a;
    if (upper(b, a)) return b;

    for (int po = PW - 1; po >= 0; po--)
        if (!upper(up[a][po], b))
            a = up[a][po];

    return up[a][0];
}

void last_dfs(int v){
    ans[v] = ad[v];

    if (v > 0)
        ans[up[v][0]] -= del[v];

    for (int u : g[v]){
        last_dfs(u);
        ans[v] += ans[u];
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

#ifdef _LOCAL
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
#endif // _LOCAL

    cin >> n >> m;

    for (int i = 0; i < n; i++) {
        cin >> a[i] >> b[i] >> c[i] >> d[i];
        vf.PB(c[i]);
        nm[i] = i;
    }

    for (int i = n; i < n + m; i++){
        cin >> a[i] >> b[i] >> c[i];
        vf.PB(a[i]);
        nm[i] = i;
    }

    sort(all(vf));

    vf.resize(unique(all(vf)) - vf.begin());

    sort(nm, nm + n + m, cmp);

    for (int it = 0; it < n + m; it++) {
        int i = nm[it];

        if (i < n)
            build(1, 0, sz(vf) - 1, c[i], b[i]);
        else build(1, 0, sz(vf) - 1, a[i], b[i]);
    }

    real_build(1, 0, sz(vf) - 1);

    for (int it = 0; it < n + m; it++){
        int i = nm[it];

        if (i < n){
            id = -1;
            search(1, 0, sz(vf) - 1, c[i], b[i], d[i]);

            pre[i] = id;

            id = i;
            update(1, 0, sz(vf) - 1, c[i], b[i], d[i]);
        } else {
            id = -1;
            search(1, 0, sz(vf) - 1, a[i], b[i], b[i]);

            if (id >= 0)
                cols[id].PB(c[i]);
        }
    }

    for (int i = 0; i < n; i++){
        g[pre[i] + 1].PB(i + 1);
        up[i + 1][0] = pre[i] + 1;

        if (sz(cols[i]) == 0) continue;

        for (int cl : cols[i])
            if (sz(ver[cl]) == 0 || ver[cl].back() != i + 1)
                ver[cl].PB(i + 1);
    }

    dfs(0);

    for (auto EL : ver){
        vector<int> &vc = EL.second;

        sort(all(vc), cmp1);

        int glc = vc[0];

        ad[vc[0]]++;
        del[vc[0]]++;

        for (int it = 1; it < sz(vc); it++){
            int v = vc[it];
            int pr = vc[it - 1];

            int lc = lca(v, pr);

            if (!upper(glc, lc)){
                ad[up[glc][0]]++;
                del[lc]++;
                glc = lc;
            }

            ad[lc]--;
            ad[v]++;
        }

        ad[up[glc][0]]++;
        del[0]++;
    }

    last_dfs(0);

    for (int i = 1; i <= n; i++)
        cout << ans[i] << '\n';

    return 0;
}

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