oj.uz

Submission #1110294

# Submission time Handle Problem Language Result Execution time Memory
1110294 2024-11-09T06:24:16 Z PVSekhar Plahte (COCI17_plahte) C++14
160 / 160
 439 ms 53208 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll N = 80000 + 5;

template<class T>
struct Point{
	T x, y;
	Point (const ll &x_ = 0, const ll &y_ = 0) : x(x_), y(y_) {};
    
	bool operator<(const Point &p) const{
    	return x < p.x || (x == p.x && y < p.y);
	}
	bool operator==(const Point &p) const{
    	return x == p.x && y == p.y;
	}
};

using Pt = Point<ll>;

struct Line {
	ll x1, y1, x2, y2, ind;
	Line (const ll &x1_ = 0, const ll &y1_ = 0, const ll &x2_ = 0, const ll &y2_ = 0, const ll &ind_ = 0) : x1(x1_), y1(y1_), x2(x2_), y2(y2_), ind(ind_) {};
};

struct SEGTREE {
    ll INF = N - 1;
    int n;
    vector<ll> lazy;
    SEGTREE(int n_) {
        n = n_;
        lazy.assign(4 * n + 1, 0);
        lazy[1] = INF;
    }
    void prop(int node, int i, int j) {
        if (lazy[node] == -1) return;
        if (i != j) {
            lazy[node << 1] = lazy[node];
            lazy[node << 1 | 1] = lazy[node];
            lazy[node] = -1;
        }
    }
    void update(int node, int l, int r, int i, int j, int val) {
        prop(node, l, r);
        if (l > r || l > j || i > j || i > r) return;
        if (i <= l && r <= j) {
            lazy[node] = val;
            return;
        }
        int mid = (l + r) / 2;
        update(node << 1, l, mid, i, j, val);
        update(node << 1 | 1, mid + 1, r, i, j, val);
    }
    void update(int i, int j, int val) {
        update(1, 1, n, i, j, val);
    }
    int query(int node, int i, int j, int ind) {
        if (i == j) return lazy[node];
        prop(node, i, j);
        int mid = (i + j) / 2;
        if (ind <= mid) return query(node << 1, i, mid, ind);
        else return query(node << 1 | 1, mid + 1, j, ind);
    }
    int query(int ind) {
        return query(1, 1, n, ind);
    }
} segtree(3 * N);

ll n, m;
vector<Line> recs;
vector<set<ll>> c_set(N);
vector<ll> c_ind(N), p(N, N - 1), ans(N, -1);
vector<pair<pair<ll, ll>, ll>> pts;
vector<vector<ll>> edges(N);
map<ll, ll> y_ind;

void merge(ll node, ll parent) {
    if (c_set[c_ind[node]].size() > c_set[c_ind[parent]].size()) {
        swap(c_ind[node], c_ind[parent]);
    }
    for (ll x : c_set[c_ind[node]]) c_set[c_ind[parent]].insert(x);
}

void sweep() {
    set<pair<ll, ll>> s;
    pair<ll, ll> pt, c_pos;
    ll ind, par = 0, flag = 0, last_col = 0;
    for (auto x : pts) {
        pt = x.first, ind = x.second;
        par = segtree.query(y_ind[pt.second]);
        if (flag) {
            flag = 0;
            if (c_pos == pt) {
                c_set[c_ind[ind]].insert(last_col);
            }
        }
        if (ind < 0) {
            if (par != N - 1) c_set[c_ind[par]].insert(ind);
            c_pos = pt;
            last_col = ind;
            flag = 1;
        } else if (s.find(make_pair(recs[ind].x1, recs[ind].y1)) == s.end()) {
            s.insert(pt);
            edges[ind].push_back(par);
            edges[par].push_back(ind);
            segtree.update(y_ind[recs[ind].y1], y_ind[recs[ind].y2], ind);
            p[ind] = par;
        } else {
            s.erase(make_pair(recs[ind].x1, recs[ind].y1));
            segtree.update(y_ind[recs[ind].y1], y_ind[recs[ind].y2], p[ind]);
        }
    }
}

void dfs(ll node, ll parent) {
    for (ll child : edges[node]) {
        if (child == parent) continue;
        dfs(child, node);
        if (node != N - 1) merge(child, node);
    }
    if (node != N - 1) ans[node] = c_set[c_ind[node]].size();
}

void solve() {
	ll a, b, c, d;
	cin >> n >> m;
    vector<ll> ys;
	for (ll i = 0; i < n; i++) {
    	cin >> a >> b >> c >> d;
    	recs.push_back(Line(a, b, c, d, i));
    	pts.push_back(make_pair(make_pair(a, b), i));
    	pts.push_back(make_pair(make_pair(c, d), i));
        ys.push_back(b);
        ys.push_back(d);
        c_ind[i] = i;
	}
	for (ll i = 0; i < m; i++) {
    	cin >> a >> b >> c;
        ys.push_back(b);
    	pts.push_back(make_pair(make_pair(a, b), -c));
	}
	sort(pts.begin(), pts.end());
	sort(ys.begin(), ys.end());
    for (ll i = 0; i < (ll)ys.size(); i++) {
        y_ind[ys[i]] = i + 1;
    }
    sweep();
    dfs(N - 1, -1);
    for (ll i = 0; i < n; i++) cout << ans[i] << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
	ll t = 1;
	// cin >> t;
	while(t--) {
    	solve();
	}
	return 0;
}

Subtask #1
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 26556 KB Output is correct
2 Correct 120 ms 27116 KB Output is correct
3 Correct 7 ms 15440 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 28792 KB Output is correct
2 Correct 132 ms 28340 KB Output is correct
3 Correct 7 ms 15612 KB Output is correct

Subtask #3
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 233 ms 39788 KB Output is correct
2 Correct 257 ms 37800 KB Output is correct
3 Correct 7 ms 15440 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 406 ms 53208 KB Output is correct
2 Correct 427 ms 51344 KB Output is correct
3 Correct 7 ms 15440 KB Output is correct

Subtask #5
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 416 ms 52476 KB Output is correct
2 Correct 439 ms 49368 KB Output is correct
3 Correct 8 ms 15440 KB Output is correct