| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
醉醉的过了#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator