18ptsTLE求调
查看原帖
18ptsTLE求调
1181602
Cute_Furina楼主2025/7/20 16:41
#include<bits/stdc++.h>
using namespace std;
#define int long long 
int tag[1000005], len[1000005], xx[1000050], n, T, t;
struct node {
	int y, lx, rx, inout;
}line[1000005];
bool cmp(node a, node b) {
	return a.y < b.y;
} 
bool InRange(int l, int r, int L, int R) {
	return (l >= L) && (r <= R);
}
bool OutofRange(int l, int r, int L, int R) {
	return (l > R) || (r < L); 
}
void pushup(int x, int l, int r) {
	if(tag[x]) len[x] = xx[r] - xx[l];
	else if(l + 1 == r){
		len[x] = 0;
	}
	else {
		len[x] = len[x * 2] + len[x * 2 + 1];
	}
}
void update(int l, int r, int io, int p, int pl, int pr) {
	if(l <= pl && pr <= r) {
		tag[p] += io;
		pushup(p, pl, pr);
	} 
	if(pl + 1 == pr) return ;
	int mid = pl + pr >> 1;
	if(l <= mid) update(l, r, io, p * 2, pl, mid);
	if(r > mid) update(l, r, io, p * 2 + 1, mid, pr); 
	pushup(p, pl, pr); 
} 
signed main() {
	int cnt = 0;
	cin >> T;
	while(T --) {
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		line[++ cnt].inout = 1;
		line[cnt].lx = x1;
		line[cnt].rx = x2;
		line[cnt].y = y1;
		xx[cnt] = x1;
		line[++ cnt].inout = -1;
		line[cnt].lx = x1;
		line[cnt].rx = x2;
		line[cnt].y = y2;
		xx[cnt] = x2;
	}	
	sort(xx + 1, xx + cnt + 1);
	sort(line + 1, line + cnt + 1, cmp);
	int num = unique(xx + 1, xx + cnt + 1) - (xx + 1);
	memset(tag, 0, sizeof(tag));
	memset(len, 0, sizeof(len));
	int ans = 0;
	for(int i = 1;i <= cnt;i ++) {
		int L, R;
		ans += len[1] * (line[i].y - line[i - 1].y);
		L = lower_bound(xx + 1, xx + num + 1, line[i].lx) - xx;
		R = lower_bound(xx + 1, xx + num + 1, line[i].rx) - xx;
		update(L, R, line[i].inout, 1, 1, num);
	}
	cout << ans; 
}
2025/7/20 16:41
加载中...