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