oj.uz

답안 #235891

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
235891 2020-05-30T10:19:28 Z Vimmer Plahte (COCI17_plahte) C++14
160 / 160
 453 ms 40552 KB 
#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], ans[N];

set <int> se[80001];

map <int, int> mp;

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

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

        set <int> st = dfs(it, v);

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

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

    ans[v] = sz(ser);

    return 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 << ans[i] << '\n';
}

Subtask #1
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 121 ms 15336 KB Output is correct
2 Correct 114 ms 14828 KB Output is correct
3 Correct 8 ms 6528 KB Output is correct

Subtask #2
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 141 ms 18540 KB Output is correct
2 Correct 142 ms 16748 KB Output is correct
3 Correct 8 ms 6528 KB Output is correct

Subtask #3
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 251 ms 28624 KB Output is correct
2 Correct 238 ms 21480 KB Output is correct
3 Correct 8 ms 6528 KB Output is correct

Subtask #4
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 453 ms 40552 KB Output is correct
2 Correct 436 ms 31312 KB Output is correct
3 Correct 8 ms 6528 KB Output is correct

Subtask #5
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 421 ms 37856 KB Output is correct
2 Correct 427 ms 29544 KB Output is correct
3 Correct 8 ms 6528 KB Output is correct