제출 #613726

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
613726		Vanilla	Plahte (COCI17_plahte)	C++17	160 / 160	646 ms	203960 KiB

plahte

#include <bits/stdc++.h>
using namespace std;
typedef long long int64;
const int maxn = 8e4 + 2;
vector <int> ad [maxn]; 
int dad [2 * maxn];
set <int> stl [maxn * 2];
int rs [maxn];
 
struct node {
    int l, r, v;
    int lazy = -1;
    node* left = NULL;
    node* right = NULL;
 
    node(int _l, int _r, int _v): l(_l), r(_r), v(_v) {};
 
    inline void propagate () {
        if (left == NULL) {
            int mid = (l + r) / 2;
            left = new node (l, mid, 0);
            right = new node (mid + 1, r, 0);
        }
        if (lazy != -1){
            left->v = left->lazy = right->v = right->lazy = lazy;
            lazy = -1;
        }
    }
 
    inline void update (int il, int ir, int nv) {
        if (l > ir || r < il) return;
        if (il <= l && r <= ir) return void(v = lazy = nv);
        propagate();
        left->update(il, ir, nv);
        right->update(il, ir, nv);
    }
 
    inline int query (int x) {
        if (l > x || r < x) return 0;
        if (l == r && l == x) return v;
        propagate();
        return max(left->query(x), right->query(x));
    }
 
};
 
struct square {
    int x1,y1,x2,y2;
} a [maxn];
 
struct event {
    int x;
    int id;
    int type; // 1 -> start square, 2 -> point, 3-> end square
 
    bool operator < (const event& oth) {
        if (x != oth.x) return x < oth.x;
        return type < oth.type;
    }
};
 
struct point {
    int x;
    int y;
    int color;
} b[maxn];
 
vector <event> ev;
int n, m;
 
set <int> *dfs (int u){
    set <int> *pt = new set <int>;
    if (u > n) {
        pt->insert(b[u - n].color);
        return pt;
    }
    for (int v: ad[u]) {
        set <int> *now = dfs(v);
        if (now->size() > pt->size()) swap(now, pt);
        for (int j: *now) pt->insert(j);
    }
    rs[u] = pt->size();
    return pt;
}
 
int main() {
    cin >> n >> m;
    node* sgt = new node (1, 1e9, 0);
    for (int i = 1; i <= n; i++){
        cin >> a[i].x1 >> a[i].y1 >> a[i].x2 >> a[i].y2;
        ev.push_back({a[i].x1, i, 1});
        ev.push_back({a[i].x2, i, 3});
    }
    for (int i = 1; i <= m; i++){
        cin >> b[i].x >> b[i].y >> b[i].color;
        ev.push_back({b[i].x, i, 2});                                                
    }
    sort(ev.begin(), ev.end());
    for (auto [x, id, type]: ev) {
        if (type == 1) {
            dad[id] = sgt->query(a[id].y2);
            ad[dad[id]].push_back(id);
            sgt->update(a[id].y1, a[id].y2, id);
        }
        if (type == 2) {
            dad[id + n] = sgt->query(b[id].y);
            ad[dad[id + n]].push_back(id + n);
        }
        if (type == 3) {
            sgt->update(a[id].y1, a[id].y2, dad[id]);
        }
    }
    dfs(0);
    for (int i = 1; i <= n; i++){
        cout << rs[i] << "\n";
    }
    delete sgt; // plbm este memory leak
    return 0;
}

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