Submission #1298972

#	Time	Username	Problem	Language	Result	Execution time	Memory
1298972		nguyenkhangninh99	절취선 (JOI14_ho_t5)	C++20	100 / 100	189 ms	22000 KiB

2014_ho_t5

#include<algorithm>
#include<iostream>
#include<vector>
#include<cstdio>
#include<set>
using namespace std;

#define int long long

struct SegmentTree{
    int n;
    vector<bool> lazy;

    SegmentTree(){
        n = 1 << 19;
        lazy.assign(2 * n, false);
    }

    void push(int id, int l, int r) {
        if (lazy[id]) {
            if (l != r) {
                lazy[2 * id] = true;
                lazy[2 * id + 1] = true;
            }
            lazy[id] = false;
        }
    }

    void set_renew(int u, int v, int id, int l, int r) {
        if (l > v || r < u) return;
        if (l >= u && r <= v) {
            lazy[id] = true;
            return;
        }
        push(id, l, r);
        int mid = (l + r) / 2;
        set_renew(u, v, 2 * id, l, mid);
        set_renew(u, v, 2 * id + 1, mid + 1, r);
    }
    void set_renew(int l, int r) { set_renew(l, r - 1, 1, 0, n - 1); }

    bool is_renew(int p, int id, int l, int r) {
        if (l == r){
            int res = lazy[id];
            lazy[id] = 0;
            return res;
        }
        push(id, l, r);
        int mid = (l + r) / 2;
        if (p <= mid) return is_renew(p, 2 * id, l, mid);
        else return is_renew(p, 2 * id + 1, mid + 1, r);
    }
    bool is_renew(int p) { return is_renew(p, 1, 0, n - 1); }

} st;

struct action{
	int pos, act, left, right;
};

const int maxn = 1e5 + 5;
int x1[maxn], y1[maxn], x2[maxn], y2[maxn];
int target[2 * maxn], bit[3 * maxn];
vector<int> lab;

void update(int p, int v){
    for(; p < 3 * maxn; p += p & -p) bit[p] += v;
}
int get(int p){
    int res = 0;
    for(; p;  p -= p & -p) res += bit[p];
    return res;
}
int find(int u){
	return (lab[u] < 0) ? u : (lab[u] = find(lab[u]));
}

bool join(int u, int v){
    u = find(u), v = find(v);

    if(u == v) return false;
    if(lab[u] > lab[v]) swap(u, v);
    lab[u] += lab[v];
    lab[v] = u; 
    return true;
}
void adjust(int p){
	if(st.is_renew(p)){
		lab.push_back(-1);
		target[p] = lab.size() - 1;
	}
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int w, h, n; cin >> w >> h >> n;
	for(int i = 0; i < n; i++){
        cin >> x1[i] >> y1[i] >> x2[i] >> y2[i];
		if(x1[i] > x2[i]) swap(x1[i], x2[i]);
		if(y1[i] > y2[i]) swap(y1[i], y2[i]);
	}
	for(int i = 0; i < 2 * n; i++) target[i] = -1;

	x1[n] = 0;
    y1[n] = 0; 
    x2[n] = w; 
    y2[n] = 0; 
	x1[n + 1] = 0; 
    y1[n + 1] = 0; 
    x2[n + 1] = 0; 
    y2[n + 1] = h;
    x1[n + 2] = w;
    y1[n + 2] = 0;
    x2[n + 2] = w;
    y2[n + 2] = h;
    x1[n + 3] = 0;
    y1[n + 3] = h;
    x2[n + 3] = w;
    y2[n + 3] = h;
	n += 4;

	vector<int> compress;
	for(int i = 0; i < n; i++){
		compress.push_back(x1[i]);
		compress.push_back(x2[i]);
	}
	compress.push_back(-1);
	sort(compress.begin(), compress.end());
	compress.erase(unique(compress.begin(), compress.end()), compress.end());

	for(int i = 0; i < n; i++){
		x1[i] = lower_bound(compress.begin(), compress.end(), x1[i]) - compress.begin();
		x2[i] = lower_bound(compress.begin(), compress.end(), x2[i]) - compress.begin();
	}

	vector<action> a;
	for(int i = 0; i < n; i++){
		if(x1[i] == x2[i]){
			a.push_back({y1[i], 0, x1[i], -1});
			a.push_back({y2[i], 2, x1[i], -1});
		}else a.push_back({y1[i], 1, x1[i], x2[i]});
	}

	sort(a.begin(), a.end(), [&](action x, action y){
        return x.pos < y.pos || (x.pos == y.pos && x.act < y.act);
    });

	set<int> s;
	s.insert(0);
	target[0] = 0;
	lab.push_back(-1);

	int res = 0;
	for(auto [pos, act, left, right]: a){
		if(act == 0){
			int lf = *--s.lower_bound(left);

			adjust(lf); 
            adjust(left);
			target[left] = target[lf];

			update(left, 1);
    		s.insert(left);
		}else if(act == 1){
			int count = get(right) - get(left - 1);
			if(count < 2) continue;
			res += count - 1;

			st.set_renew(left, *--s.upper_bound(right));
		}else{
			int lf = *--s.lower_bound(left);
			adjust(lf); 
            adjust(left);
			if(join(target[lf], target[left])) res--;

			update(left, -1);
            s.erase(left);
		}
	}

    cout << res;
}

Compilation message (stderr)

2014_ho_t5.cpp:62:15: warning: built-in function 'y1' declared as non-function [-Wbuiltin-declaration-mismatch]
   62 | int x1[maxn], y1[maxn], x2[maxn], y2[maxn];
      |               ^~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 50 / 50