oj.uz

Submission #234634

# Submission time Handle Problem Language Result Execution time Memory
234634 2020-05-24T21:13:21 Z VEGAnn Plahte (COCI17_plahte) C++14
160 / 160
 313 ms 34272 KB 
#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> cols[N], g[N];
set<a3> st;
set<a3>::iterator iter;
vector<a3> vf;
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 cmp1(int _x, int _y){
    return tin[_x] < tin[_y];
}

int get_pre(int vl){
    iter = st.lower_bound({vl, 0, 0});

    if (iter == st.end()) return -1;

    if ((*iter)[1] == -1)
        return pre[(*iter)[2]];
    else return (*iter)[2];
}

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({a[i], -1, i});
        vf.PB({c[i], +1, i});
    }

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

    sort(all(vf));

    st.clear();

    for (a3 cr : vf){
        int i = cr[2];

        if (cr[1] == -1){
            pre[i] = get_pre(d[i]);

            st.insert({b[i], -1, i});
            st.insert({d[i], +1, i});
        } else if (cr[1] == 0){
            int id = get_pre(b[i]);

            if (id >= 0)
                cols[id].PB(c[i]);
        } else {
            st.erase({b[i], -1, i});
            st.erase({d[i], +1, 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
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 15596 KB Output is correct
2 Correct 77 ms 16488 KB Output is correct
3 Correct 10 ms 9728 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 18536 KB Output is correct
2 Correct 106 ms 18028 KB Output is correct
3 Correct 10 ms 9728 KB Output is correct

Subtask #3
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 25060 KB Output is correct
2 Correct 161 ms 22624 KB Output is correct
3 Correct 11 ms 9856 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 313 ms 34272 KB Output is correct
2 Correct 283 ms 29796 KB Output is correct
3 Correct 10 ms 9728 KB Output is correct

Subtask #5
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 308 ms 32740 KB Output is correct
2 Correct 266 ms 29368 KB Output is correct
3 Correct 10 ms 9856 KB Output is correct