Submission #341886

#	Time	Username	Problem	Language	Result	Execution time	Memory
341886		phathnv	Plahte (COCI17_plahte)	C++11	160 / 160	454 ms	53104 KiB

plahte

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct Trectangle{
    int x, y, u, v, ind;
};

struct Tball{
    int x, y, c;
};

struct Tdata{
    int t, type, l, r, ind;
    Tdata(int _t, int _type, int _l, int _r, int _ind){
        t = _t;
        type = _type;
        l = _l;
        r = _r;
        ind = _ind;
    }
};

struct TsegmentTree{
    int n;
    vector <vector<int>> d;

    void insert(int id, int l, int r, int u, int v, int val){
        if (v < l || r < u)
            return;
        if (u <= l && r <= v){
            d[id].push_back(val);
            return;
        }
        int mid = (l + r) >> 1;
        insert(id << 1, l, mid, u, v, val);
        insert(id << 1 | 1, mid + 1, r, u, v, val);
    }
    void remove(int id, int l, int r, int u, int v){
        if (v < l || r < u)
            return;
        if (u <= l && r <= v){
            d[id].pop_back();
            return;
        }
        int mid = (l + r) >> 1;
        remove(id << 1, l, mid, u, v);
        remove(id << 1 | 1, mid + 1, r, u, v);
    }
    int find(int id, int l, int r, int u, int v){
        if (v < l || r < u)
            return -1;
        if (u <= l && r <= v){
            if (d[id].empty())
                return -1;
            return d[id].back();
        }
        int mid = (l + r) >> 1;
        int res = find(id << 1, l, mid, u, v);
        if (res == -1)
            res = find(id << 1 | 1, mid + 1, r, u, v);
        if (res == -1 && !d[id].empty())
            res = d[id].back();
        return res;
    }

    void init(int _n){
        n = _n;
        d.assign(n * 4 + 1, vector<int>());
    }
    void insert(int l, int r, int ind){
        insert(1, 1, n, l, r, ind);
    }
    void remove(int l, int r){
        remove(1, 1, n, l, r);
    }
    int find(int l, int r){
        return find(1, 1, n, l, r);
    }
};

const int mxN = 80001;

int n, m, answer[mxN];
Trectangle rec[mxN];
Tball b[mxN];
vector <int> adj[mxN];
set <int> color[mxN];
bool vst[mxN];

void ReadInput(){
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        cin >> rec[i].x >> rec[i].y >> rec[i].u >> rec[i].v;
        rec[i].ind = i;
    }
    for(int i = 1; i <= m; i++)
        cin >> b[i].x >> b[i].y >> b[i].c;
}

void Compress(){
    vector <int> x, y;
    for(int i = 1; i <= n; i++){
        x.push_back(rec[i].x);
        x.push_back(rec[i].u);
        y.push_back(rec[i].y);
        y.push_back(rec[i].v);
    }
    for(int i = 1; i <= m; i++){
        x.push_back(b[i].x);
        y.push_back(b[i].y);
    }
    sort(x.begin(), x.end());
    sort(y.begin(), y.end());
    x.resize(unique(x.begin(), x.end()) - x.begin());
    y.resize(unique(y.begin(), y.end()) - y.begin());

    for(int i = 1; i <= n; i++){
        rec[i].x = lower_bound(x.begin(), x.end(), rec[i].x) - x.begin() + 1;
        rec[i].u = lower_bound(x.begin(), x.end(), rec[i].u) - x.begin() + 1;
        rec[i].y = lower_bound(y.begin(), y.end(), rec[i].y) - y.begin() + 1;
        rec[i].v = lower_bound(y.begin(), y.end(), rec[i].v) - y.begin() + 1;
    }
    for(int i = 1; i <= m; i++){
        b[i].x = lower_bound(x.begin(), x.end(), b[i].x) - x.begin() + 1;
        b[i].y = lower_bound(y.begin(), y.end(), b[i].y) - y.begin() + 1;
    }
}

void Sweepline(){
    vector <Tdata> event;
    for(int i = 1; i <= n; i++){
        event.push_back(Tdata(rec[i].y, 1, rec[i].x, rec[i].u, i));
        event.push_back(Tdata(rec[i].v + 1, -1, rec[i].x, rec[i].u, i));
    }
    for(int i = 1; i <= m; i++)
        event.push_back(Tdata(b[i].y, 2, b[i].x, b[i].x, b[i].c));
    sort(event.begin(), event.end(), [](const Tdata &a, const Tdata &b){
            if (a.t != b.t)
                return a.t < b.t;
            return a.type < b.type;
         });

    int maxX = 0;
    for(int i = 1; i <= n; i++)
        maxX = max(maxX, rec[i].u);
    for(int i = 1; i <= m; i++)
        maxX = max(maxX, b[i].x);
    TsegmentTree ST;
    ST.init(maxX);

    for(Tdata e : event)
        if (e.type == -1){
            ST.remove(e.l, e.r);
        } else if (e.type == 1){
            int tmp = ST.find(e.l, e.r);
            ST.insert(e.l, e.r, e.ind);
            if (tmp != -1){
                adj[tmp].push_back(e.ind);
                //cerr << "edge " << tmp << ' ' << e.ind << endl;
            }
        } else {
            int tmp = ST.find(e.l, e.r);
            if (tmp != -1){
                color[tmp].insert(e.ind);
                //cerr << "col " << tmp << ' ' << e.ind << endl;
            }
        }
}

void Merge(set<int> &a, set<int> &b){
    if (a.size() < b.size())
        swap(a, b);
    for(int x : b)
        a.insert(x);
    b.clear();
}

void Dfs(int u){
    if (vst[u])
        return;
    vst[u] = 1;
    for(int v : adj[u]){
        Dfs(v);
        Merge(color[u], color[v]);
    }
    answer[u] = color[u].size();
}

void Solve(){
    for(int i = 1; i <= n; i++)
        Dfs(i);
    for(int i = 1; i <= n; i++)
        cout << answer[i] << '\n';
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ReadInput();
    Compress();
    Sweepline();
    Solve();
    return 0;
}

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