oj.uz

Submission #1110006

# Submission time Handle Problem Language Result Execution time Memory
1110006 2024-11-08T12:29:42 Z PVSekhar Plahte (COCI17_plahte) C++14
0 / 160
 443 ms 62100 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll N = 80000 + 2;

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 def = N - 1;
    vector<ll> tree, lazy;
    SEGTREE(int n_) {
        for (int i = 0; i < 4 * n_; i++) tree.push_back(0);
        for (int i = 0; i < 4 * n_; i++) lazy.push_back(def);
    }
    void prop(int node, int i, int j) {
        if (lazy[node] == -1) return;
        tree[node] = (j - i + 1) * lazy[node];
        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) {
        if (l > r || l > j || i > j || i > r) return;
        if (i <= l && r <= j) {
            lazy[node] = val;
            prop(node, l, r);
            return;
        }
        int mid = (l + r) / 2;
        prop(node << 1, l, mid);
        prop(node << 1 | 1, mid + 1, r);
        update(node << 1, l, mid, i, j, val);
        update(node << 1 | 1, mid + 1, r, i, j, val);
        tree[node] = tree[node << 1] + tree[node << 1 | 1];
    }
    int query(int node, int i, int j, int ind) {
        prop(node, i, j);
        if (i == j) {
            return tree[node];
        }
        int mid = (i + j) / 2;
        prop(node << 1, i, mid);
        prop(node << 1 | 1, mid + 1, j);
        tree[node] = tree[node << 1] + tree[node << 1 | 1];
        if (ind <= mid) return query(node << 1, i, mid, ind);
        else return query(node << 1 | 1, mid + 1, j, 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<Pt, 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<Pt> s;
    Pt pt;
    ll ind;
    for (auto x : pts) {
        pt = x.first, ind = x.second;
        ll par = segtree.query(1, 1, 3 * N, y_ind[pt.y]);
        if (ind < 0) {
            if (par != N - 1) c_set[c_ind[par]].insert(ind);
        } else if (s.find(Pt(recs[ind].x1, recs[ind].y1)) == s.end()) {
            s.insert(pt);
            edges[ind].push_back(par);
            edges[par].push_back(ind);
            segtree.update(1, 1, 3 * N, y_ind[recs[ind].y1], y_ind[recs[ind].y2], ind);
        } else {
            s.erase(Pt(recs[ind].x1, recs[ind].y1));
            segtree.update(1, 1, 3 * N, 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(Pt(a, b), i));
    	pts.push_back(make_pair(Pt(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(Pt(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
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 119 ms 34776 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 150 ms 37716 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 268 ms 48680 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 443 ms 62100 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 424 ms 60816 KB Output isn't correct
2 Halted 0 ms 0 KB -