Submission #235887

#	Time	Username	Problem	Language	Result	Execution time	Memory
235887		Vimmer	Plahte (COCI17_plahte)	C++14	0 / 160	1521 ms	524292 KiB

plahte

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("fast-math")
//#pragma GCC optimize("no-stack-protector")

#define F first
#define S second
#define sz(x) int(x.size())
#define pb push_back
#define N 100001
#define M ll(998244353)
#define inf 1e9 + 1e9

using namespace std;
//using namespace __gnu_pbds;

typedef long double ld;
typedef long long ll;
typedef short int si;
//typedef tree <int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

int n, m;

vector <array <int, 3> > gr;

vector <int> g[N];

int xl[N], yl[N], xr[N], yr[N], X[N], Y[N], C[N], t[N * 16], pred[N];

set <int> se[80001];

map <int, int> mp;

void dfs(int v, int p)
{
    set <int> ser = se[v];

    for (auto it : g[v])
    {
        if (it == p) continue;

        dfs(it, v);

        set <int> st = se[it];

        if (sz(st) > sz(ser)) swap(ser, st);

        for (auto it : st) ser.insert(it);
    }

    se[v] = ser;
}
void Push(int v)
{
    if (t[v] == -1) return;

    t[v + v] = t[v];

    t[v + v + 1] = t[v];

    t[v] = -1;
}

int fnd(int v, int tl, int tr, int pos)
{
    if (tl == tr) return t[v];

    Push(v);

    int md = (tl + tr) >> 1;

    if (pos <= md) return fnd(v + v, tl, md, pos);

    return fnd(v + v + 1, md + 1, tr, pos);
}

void upd(int v, int tl, int tr, int l, int r, int val)
{
    if (l > r || tl > tr || r < tl || tr < l) return;

    if (l <= tl && tr <= r)
    {
        t[v] = val;

        return;
    }

    Push(v);

    int md = (tl + tr) >> 1;

    upd(v + v, tl, md, l, r, val);

    upd(v + v + 1, md + 1, tr, l, r, val);
}

int main()
{
    //freopen("input.txt", "r", stdin); //freopen("output4.txt", "w", stdout);

    ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> m;

    vector <int> vr; vr.clear();

    for (int i = 1; i <= n; i++)
    {
        cin >> xl[i] >> yl[i] >> xr[i] >> yr[i];

        vr.pb(yl[i]);

        vr.pb(yr[i]);
    }

    for (int i = 1; i <= m; i++)
    {
        cin >> X[i] >> Y[i] >> C[i];

        vr.pb(Y[i]);
    }

    sort(vr.begin(), vr.end());

    int r = 0;

    for (int i = 0; i < sz(vr); i++)
        if (i == 0 || vr[i] != vr[i - 1]) mp[vr[i]] = r++;

    for (int i = 1; i <= m; i++)  Y[i] = mp[Y[i]];

    for (int i = 1; i <= n; i++) {yl[i] = mp[yl[i]]; yr[i] = mp[yr[i]];}

    r--;

    for (int i = 1; i <= n; i++) {gr.pb({xl[i], 0, i}); gr.pb({xr[i], 2, i});}

    for (int i = 1; i <= m; i++) gr.pb({X[i], 1, i});

    sort(gr.begin(), gr.end());

    for (auto it : gr)
    {
        int nm = it[2];

        if (it[1] == 0)
        {
            pred[nm] = fnd(1, 0, r, yl[nm]);

            g[pred[nm]].pb(nm);

            upd(1, 0, r, yl[nm], yr[nm], nm);

            continue;
        }

        if (it[1] == 1)
        {
            se[fnd(1, 0, r, Y[nm])].insert(C[nm]);

            continue;
        }

        upd(1, 0, r, yl[nm], yr[nm], pred[nm]);
    }

    dfs(0, -1);

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

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