oj.uz

Submission #916823

# Submission time Handle Problem Language Result Execution time Memory
916823 2024-01-26T14:45:49 Z sleepntsheep Plahte (COCI17_plahte) C++17
160 / 160
 356 ms 106080 KB 
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cmath>
#include <cassert>
#include <cstring>
#include <vector>
#include <algorithm>
#include <deque>
#include <set>
#include <utility>
#include <array>
#include <complex>

using u32 = unsigned;
using i32 = int;
using i64 = long long;
using u64 = unsigned long long;
using f64 = double;
using f80 = long double;

using namespace std;
using pt = complex<f80>;
#define ALL(x) begin(x), end(x)
#define ShinLena cin.tie(nullptr)->sync_with_stdio(false);
#define N 500005

int n, m;
array<int, 4> a[N];
array<int, 3> b[N];

vector<tuple<int, int, int>> ev_x;

set<pair<int, int>> fw[N];

void input_c()
{
    cin >> n >> m;

    vector<int> cord_x, cord_y;
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < 4; ++j) cin >> a[i][j];
        cord_x.push_back(a[i][0]);
        cord_x.push_back(a[i][2]);
        cord_y.push_back(a[i][1]);
        cord_y.push_back(a[i][3]);
    }
    for (int i = 0; i < m; ++i)
    {
        cin >> b[i][0] >> b[i][1] >> b[i][2];
        cord_x.push_back(b[i][0]);
        cord_y.push_back(b[i][1]);
    }
    sort(ALL(cord_x));
    sort(ALL(cord_y));
    for (int i = 0; i < n; ++i)
    {
        a[i][0] = lower_bound(ALL(cord_x), a[i][0]) - cord_x.begin() + 1;
        a[i][2] = lower_bound(ALL(cord_x), a[i][2]) - cord_x.begin() + 1;
        a[i][1] = lower_bound(ALL(cord_y), a[i][1]) - cord_y.begin() + 1;
        a[i][3] = lower_bound(ALL(cord_y), a[i][3]) - cord_y.begin() + 1;
    }
    for (int i = 0; i < m; ++i)
    {
        b[i][0] = lower_bound(ALL(cord_x), b[i][0]) - cord_x.begin() + 1;
        b[i][1] = lower_bound(ALL(cord_y), b[i][1]) - cord_y.begin() + 1;
    }

}

int par[N], parball[N];

int lz[N<<2], t[N<<2];

void push(int v, int l, int r)
{
    if (lz[v] != -86)
    {
        if (l != r) lz[2*v+1] = lz[2*v+2] = lz[v];
        t[v] = lz[v];
        lz[v] = -86;
    }
}
 
void upd(int v, int l, int r, int x, int y, int k)
{
    push(v, l, r);
    if (r < x||y<l)return;
    if(x<=l&&r<=y){lz[v]=k;push(v,l,r);return;}
    upd(2*v+1, l,(l+r)/2,x,y,k),upd(2*v+2,(l+r)/2+1,r,x,y,k);
}
 
int qry(int v,int l,int r,int p)
{
    push(v,l,r);
    if (l==r)return t[v];
    if(p<=(l+r)/2)return qry(2*v+1,l,(l+r)/2,p);
    return qry(2*v+2, (l+r)/2+1, r, p);
}


set<int> st[N];
basic_string<int> g[N];
int vis[N], ans[N], _prev[N];

void dfs(int u)
{
    if (vis[u]) return;
    vis[u] = 1;
    for (auto v : g[u]) 
    {
        dfs(v);
        if (st[v].size() > st[u].size()) st[v].swap(st[u]);
        for (auto x : st[v]) st[u].insert(x);
    }
    ans[u] = st[u].size();
}


int main()
{
    for (int i = 0; i < (N<<2); ++i) lz[i] = -86;
    ShinLena;
    input_c();

    for (int i = 0; i < n; ++i)
        ev_x.emplace_back(a[i][0], -3, i),
        ev_x.emplace_back(a[i][2], -1, i);

    for (int i = 0; i < m; ++i) ev_x.emplace_back(b[i][0], -2, i);

    sort(ALL(ev_x));

    upd(0, 1, N, 1, N, -1);
    for (auto [x, ty, id] : ev_x)
    {
        if (ty == -1)
        {
            upd(0, 1, N, a[id][1], a[id][3], par[id]);
        }
        else if (ty == -3)
        {
            par[id] = qry(0, 1, N, a[id][1]);
            if (par[id] + 1)
                g[par[id]].push_back(id);

            upd(0, 1, N, a[id][1], a[id][3], id);
        }
        else
        {
            parball[id] = qry(0, 1, N, b[id][1]);
            if (parball[id] != -1)
                st[parball[id]].insert(b[id][2]);
        }
    }

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

    return 0;
}

Subtask #1
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 92260 KB Output is correct
2 Correct 106 ms 94596 KB Output is correct
3 Correct 21 ms 84576 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 92880 KB Output is correct
2 Correct 147 ms 94292 KB Output is correct
3 Correct 23 ms 84532 KB Output is correct

Subtask #3
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 218 ms 98160 KB Output is correct
2 Correct 190 ms 100992 KB Output is correct
3 Correct 21 ms 84572 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 317 ms 103816 KB Output is correct
2 Correct 354 ms 105936 KB Output is correct
3 Correct 22 ms 84572 KB Output is correct

Subtask #5
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 314 ms 102708 KB Output is correct
2 Correct 356 ms 106080 KB Output is correct
3 Correct 26 ms 84572 KB Output is correct