HDU4509-湫湫系列故事——減肥記II（線段樹）

湫湫系列故事——減肥記II

Time Limit: 5000/2000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 2395 Accepted Submission(s): 1018


Problem Description 　　雖然制定了減肥食譜，但是湫湫顯然克制不住吃貨的本能，根本沒有按照食譜行動！
於是，結果顯而易見…
　　但是沒有什麼能難倒高智商美女湫湫的，她決定另尋對策——吃沒關系，咱吃進去再運動運動消耗掉不就好了？
　　湫湫在內心咆哮：“我真是天才啊~\(≧▽≦)/~”

　　可是，大家要知道，過年回家多忙啊——幫忙家裡做大掃除，看電影，看小說，高中同學聚餐，初中同學聚餐，小學同學聚餐，吃東西，睡覺，吃東西，睡覺，吃東西，睡覺……所以鍛煉得抽著時間來。

　　但是，湫湫實在太忙了，所以沒時間去算一天有多少時間可以用於鍛煉，現在她把每日行程告訴你，拜托你幫忙算算吧~

　　皮埃斯：一天是24小時，每小時60分鐘
Input 輸入數據包括多組測試用例。
每組測試數據首先是一個整數n，表示當天有n件事要做。
接下來n行，第i行是第i件事的開始時間和結束時間，時間格式為HH:MM。

[Technical Specification]
1. 1 <= n <= 500000
2. 00 <= HH <= 23
3. 00 <= MM <= 59

Output 請輸出一個整數，即湫湫當天可以用於鍛煉的時間（單位分鐘）
Sample Input

1
15:36 18:40
4
01:35 10:36
04:54 22:36
10:18 18:40
11:47 17:53

Sample Output

1256
179

Hint 
大量輸入，建議用scanf讀數據。
  

水的線段樹。。。。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
const int maxn = 2000;
struct node{
    int lson,rson;
    bool flag;
    int mid(){
        return (lson+rson)>>1;
    }
}tree[maxn*4];
void pushUp(int rt){
    tree[rt].flag = tree[rt<<1].flag&&tree[rt<<1|1].flag;
}
void build(int L,int R,int rt){
    tree[rt].lson = L;
    tree[rt].rson = R;
    tree[rt].flag = false;
    if(L==R)   return;
    int mid = tree[rt].mid();
    build(L,mid,rt<<1);
    build(mid+1,R,rt<<1|1);
}
void update(int L,int R,int l,int r,int rt){
    if(tree[rt].flag) return;
    if(L <= l && R >= r){
        tree[rt].flag = true;
        return;
    }
    int mid = tree[rt].mid();
    if(L <= mid){
        update(L,R,l,mid,rt<<1);
    }
    if(R > mid){
        update(L,R,mid+1,r,rt<<1|1);
    }
    pushUp(rt);
}
int query(int L,int R,int l,int r,int rt){
    if(tree[rt].flag){
        return r-l+1;
    }
    if(l==r) return 0;
    int mid = tree[rt].mid();
    int ret = 0;
    if(L <= mid) ret += query(L,R,l,mid,rt<<1);
    if(R > mid) ret += query(L,R,mid+1,r,rt<<1|1);
    return ret;
}
int main(){

    int n;
    while(~scanf("%d",&n)){
        build(0,1439,1);
        while(n--){
            int a,b,c,d;
            scanf("%d:%d %d:%d",&a,&b,&c,&d);
            update(a*60+b+1,c*60+d,0,1439,1);
        }
        printf("%d\n",1440-query(0,1439,0,1439,1));
    }
    return 0;
}