Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

醉醉的过了

Posted by astoninfer at 2015-10-01 21:38:48 on Problem 2528
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#define lson (u << 1)
#define rson (u << 1 | 1)
using namespace std;
const int maxn = 1e4 + 10;
const int maxm = 1e7 + 10;
int mapi[maxm];
struct Seg{
	int l, r, v, lazy;
}seg[maxn << 3];
bool vis[maxn];
int n, N;
int a[maxn], b[maxn];
int c[maxn << 1];

void build(int u, int l, int r){
	seg[u].l = l, seg[u].r = r;
	seg[u].v = -1;
	seg[u].lazy = 0;
	if(r - l < 2) return;
	int mid = (l + r) >> 1;
	build(lson, l, mid);
	build(rson, mid, r);
}

void push_down(int u){
	if(seg[u].lazy && seg[u].r - seg[u].l > 1){
		seg[lson].v = seg[rson].v = seg[u].v;
		seg[u].lazy = 0;
		seg[lson].lazy = seg[rson].lazy = 1;
	}
}
void query(int u, int l, int r){
	if(seg[u].v > 0){
		vis[seg[u].v] = 1;
		return;
	}
	push_down(u);
	int mid = (l + r) >> 1;
	query(lson, l, mid);
	query(rson, mid, r);
}

void push_up(int u){
	seg[u].v = -1;
}

void update(int u, int l, int r, int L, int R, int v){
	if(l == L && r == R){
		seg[u].v = v;
		seg[u].lazy = 1;
		return;
	}
	push_down(u);
	int mid = (l + r) >> 1;
	if(R <= mid) update(lson, l, mid, L, R, v);
	else if(L >= mid) update(rson, mid, r, L, R, v);
	else{
		update(lson, l, mid, L, mid, v);
		update(rson, mid, r, mid, R, v);
	}
	push_up(u);
}

int main(){
	//freopen("in.txt", "r", stdin);
	scanf("%d", &N);
	while(N--){
		scanf("%d", &n);
		for(int i = 1, k = 1; i <= n; i++){
			scanf("%d%d", &a[i], &b[i]);
			c[k++] = a[i], c[k++] = b[i];
		}
		int base = 0, len = n << 1;
		sort(c + 1, c + len + 1);
		c[0] = -1;
		for(int i = 1; i <= len; i++){
			mapi[c[i]] = c[i] > c[i - 1] ? ++base : base;
		}
		build(1, 1, base + 1);
		memset(vis, 0, sizeof vis);
		for(int i = 1; i <= n; i++){
			int x = mapi[a[i]], y = mapi[b[i]];
			update(1, 1, base + 1, x, y + 1, i);
		}
		query(1, 1, base + 1);
		int ans = 0;
		for(int i = 1; i <= n; i++) ans += vis[i];
		printf("%d\n", ans);
	}
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator