oj.uz

Submission #235876

# Submission time Handle Problem Language Result Execution time Memory
235876 2020-05-30T09:45:47 Z Vimmer Plahte (COCI17_plahte) C++14
0 / 160
 2000 ms 524292 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];

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;
}
void bld(int v, int tl, int tr)
{
    t[v] = -1;

    if (tl == tr) return;

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

    bld(v + v, tl, md);

    bld(v + v + 1, md + 1, tr);
}

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 = 0; i < n; i++)
    {
        cin >> xl[i] >> yl[i] >> xr[i] >> yr[i];

        vr.pb(yl[i]);

        vr.pb(yr[i]);
    }

    for (int i = 0; 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 = 0; i < m; i++)  Y[i] = mp[Y[i]];

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

    r--;

    bld(1, 0, r);

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

    for (int i = 0; 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)
        {
            int id = fnd(1, 0, r, yl[nm]);

            if (id != -1) g[id].pb(nm);

            pred[nm] = id;

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

            continue;
        }

        if (t[1] == 1)
        {
            int id = fnd(1, 0, r, Y[nm]);

            if (id != -1) se[id].insert(C[nm]);

            continue;
        }

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

    dfs(0, -1);

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

Subtask #1
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 113 ms 15344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 139 ms 16748 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 32.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2121 ms 514260 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 391 ms 32360 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Runtime error 756 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -