Submission #1048233

#	Time	Username	Problem	Language	Result	Execution time	Memory
1048233		Leo121	Plahte (COCI17_plahte)	C++17	64 / 160	243 ms	44408 KiB

plahte

#include <bits/stdc++.h>

#define pb push_back
#define rbg(v) v.rbegin()
#define bg(v) v.begin()
#define all(v) bg(v), v.end()
#define SZ(v) int(v.size())
#define MP make_pair
#define fi first
#define se second
#define forn(i, a, b) for(int i = int(a); i <= int(b); ++ i)
#define for0(i, n) forn(i, 0, n - 1)
#define for1(i, n) forn(i, 1, n)
#define fora(i, a, b) for(int i = int(a); i >= int(b); -- i)
#define far0(i, n) fora(i, n - 1, 0)
#define far1(i, n) fora(i, n, 1)
#define foru(i, v) for(auto & i : v)
#define lb lower_bound
#define ub upper_bound
#define ord1(s, n) s + 1, s + int(n) + 1
#define ord0(s, n) s, s + int(n)
#define debug(x) cout << #x << " = " << x << endl

using namespace std;

///#include <bits/extc++.h>
///using namespace __gnu_pbds;
///typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ost;

typedef unsigned long long ull;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ll> vl;
typedef vector<ii> vii;
typedef vector<bool> vb;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
typedef long double ld;
typedef double db;
typedef __int128 Int;

const int mod = 1e9 + 7;
const int mod2 = 998244353;
///const int inf = 1e4;

const int MX = 8e4;

struct point{
    int x, y;
    point() : x(0), y(0) {}
    point(int x, int y) : x(x), y(y) {}
};

istream &operator>>(istream &is, point & p){return is >> p.x >> p.y;}
ostream &operator<<(ostream &os, const point & p){return os << "(" << p.x << ", " << p.y << ")";}

struct rectangle{
    point llc, urc;
    rectangle() : llc(), urc() {}
    rectangle(point llc, point urc) : llc(llc), urc(urc) {}
};

int p[MX];
vi tree[MX];
int st[12 * MX + 4];
int ans[MX];
vi shot[MX];
vector<rectangle> sheets;
vector<point> balls;
vi colour;

void build(int node, int l, int r){
    st[node] = -1;
    if(l == r) return;
    int m = (l + r) / 2;
    build(node * 2, l, m);
    build(node * 2 + 1, m + 1, r);
}

void push(int node, int l, int r){
    if(l == r) return;
    if(st[node] == -1) return;
    st[node * 2] = st[node];
    st[node * 2 + 1] = st[node];
    st[node] = -1;
}

int query(int node, int l, int r, int p){
    push(node, l, r);
    if(l == r) return st[node];
    int m = (l + r) / 2;
    if(p <= m) return query(node * 2, l, m, p);
    return query(node * 2 + 1, m + 1, r, p);
}

void update(int node, int l, int r, int a, int b, int val){
    push(node, l, r);
    if(l > b || r < a) return;
    if(a <= l && r <= b){
        if(l == r){
            st[node] = val;
            return;
        }
        st[node * 2] = val;
        st[node * 2 + 1] = val;
        return;
    }
    int m = (l + r) / 2;
    update(node * 2, l, m, a, b, val);
    update(node * 2 + 1, m + 1, r, a, b, val);
}

struct ure{
    int x, t, id;
    const bool operator < (const ure & b) const {
        if(x == b.x)
            return t < b.t;
        return x < b.x;
    }
};

set<int> *cnt[MX];
void dfs(int u){
    int mx = -1, bigchild = -1;
    for(auto v : tree[u]){
        dfs(v);
        if(SZ((*cnt[v])) > mx){
            mx = SZ((*cnt[v]));
            bigchild = v;
        }
    }
    cnt[u] = (bigchild == -1) ? new set<int>() : cnt[bigchild];
    foru(c, shot[u])
        (*cnt[u]).insert(c);
    for(auto v : tree[u]){
        if(v == bigchild) continue;
        for(auto x : (*cnt[v]))
            (*cnt[u]).insert(x);
    }
    ans[u] = SZ((*cnt[u]));
}

void solve(){
    map<int, int> mp;
    int n, m;
    cin >> n >> m;
    sheets.resize(n);
    balls.resize(m);
    colour.resize(m);
    for0(i, n){
        cin >> sheets[i].llc >> sheets[i].urc;
        mp[sheets[i].llc.y] = 1;
        mp[sheets[i].urc.y] = 1;
    }
    for0(i, m){
        cin >> balls[i] >> colour[i];
        mp[balls[i].y] = 1;
    }
    int id = 0;
    for(auto & [key, val] : mp)
        val = ++ id;
    vector<ure> event;
    event.reserve(2 * n + m);
    for0(i, n){
        sheets[i].llc.y = mp[sheets[i].llc.y];
        sheets[i].urc.y = mp[sheets[i].urc.y];
        event.pb({sheets[i].llc.x, 0, i});
        event.pb({sheets[i].urc.x, 2, i});
    }
    for0(i, m){
        balls[i].y = mp[balls[i].y];
        event.pb({balls[i].x, 1, i});
    }
    sort(all(event));
    memset(p, -1, sizeof(p));
    build(1, 1, id);
    int idx, t, aux;
    for0(i, 2 * n + m){
        idx = event[i].id;
        t = event[i].t;
        if(!t){
            p[idx] = query(1, 1, id, sheets[idx].llc.y);
            if(p[idx] != -1) tree[p[idx]].pb(idx);
            update(1, 1, id, sheets[idx].llc.y, sheets[idx].urc.y, idx);
            continue;
        }
        if(t == 1){
            aux = query(1, 1, id, balls[idx].y);
            if(aux != -1)
                shot[aux].pb(colour[idx]);
            continue;
        }
        update(1, 1, id, sheets[idx].llc.y, sheets[idx].urc.y, p[idx]);
    }
    for0(u, n)
        if(p[u] == -1)
            dfs(u);
    for0(u, n)
        cout << ans[u] << '\n';
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ///freopen("squares.in", "r", stdin);
    ///freopen("squares.out", "w", stdout);
    int t = 1;
    ///cin >> t;
    for1(i, t){
        ///cout << "Case " << i << ": ";
        solve();
        ///cout << '\n';
    }

    return 0;
}

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