Light oj 1207 Solution (SEGMENT TREE)

INPUT:

1

5

1 4

2 6

8 10

3 4

7 10

OUTPUT:
Case 1: 4

For each case, print the case number and the number of posters with visible sections.

#include <set>
#include <map>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <cctype>
#include <cstdio>
#include <iomanip>
#include <sstream>
#include <cstdlib>
#include <cassert>
#include <climits>
#include <complex>
#include <numeric>
#include <valarray>
#include <iostream>
#include <memory.h>
#include <algorithm>
using namespace std;
#define inf (1<<29)
#define pb push_back
#define mp make_pair
#define eps 1e-9
#define nl printf("\n")
#define spc printf(" ")
#define sci(n) scanf("%ld",&n)
#define sc64(n) scanf("%I64d",&n)
#define scii(a,b) scanf("%ld %ld",&a,&b)
#define sc6464(a,b) scanf("%I64d %I64d",&a,&b)
#define scs(s) scanf("%s",s)
#define scss(a,b) scanf("%s %s",a,b)
#define scd(f) scanf("%lf",&f)
#define scdd(a,b) scanf("%lf %lf",&a,&b)
#define pfi(a) printf("%ld",a)
#define pf64(a) printf("%I64d",a)
#define pfii(a,b) printf("%ld %ld",a,b)
#define pf6464(a,b) printf("%I64d %I64d",a,b)
#define pfs(a) printf("%s",a)
#define pfss(a,b) printf("%s %s",a,b)
#define pfd(a) printf("%lf",a)
#define pfdd(a,b) printf("%lf %lf",a,b)
#define rep(i,n) for(int i(0),_n(n);i<_n;++i)
#define repr(i,n) for(int i=n;i>=0;i--)
#define repi(i,a,b) for(int i(a),_b(b);i<=_b;++i)
#define repl(i,n) for(int i(1),_n(n);i<=_n;++i)
#define repir(i,a,b) for(int i=a;i>=b;i--)
#define ff first
#define ss second
#define all(a) a.begin(),a.end()
#define mem(x,a) memset(x,a,sizeof(x))
#define repe(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();++it)
int dx[]= {0,0,1,-1,1,-1,1,-1},dy[]= {1,-1,0,0,1,-1,-1,1};
typedef vector<int> vi;
typedef vector<long> vl;
typedef vector<long long> vll;
typedef vector<string> vs;
#define ll long long
typedef vector<vector<int> > vvi;
#else
#define debug(args...)
#endif
#define MX 300000
long long tree[3*MX];
long long ar[MX],tr[3*MX];
set<long>st;
int qq(long l,long r,long i,long j,long node,long valu)
{
    if(i>r||j<l)
        return 0;
    if(tree[node]!=-1)
    {
        if(r!=l)
        {
            tree[node*2]=tree[node];
            tree[node*2+1]=tree[node];
            tree[node]=-1;
        }
    }
    if(i<=l&&j>=r)
    {
        tree[node]=valu;
        return 0;
    }
    long mid=(l+r)/2;
    long left=2*node;
    long right=left+1;
    qq(l,mid,i,j,left,valu);
    qq(mid+1,r,i,j,right,valu);
}
int q(long l,long r,long node)
{
    if(tree[node]!=-1)
    {
        st.insert(tree[node]);
        return 0;
    }
    if(r==l)
        return 0;
    long mid=(l+r)/2;
    long left=2*node;
    long right=left+1;
    q(l,mid,left);
    q(mid+1,r,right);
}
int main()
{
    long t,k;
    scanf("%ld",&t);
    for(long k=1; k<=t; k++)
    {
        long N=1,n,m,f,l,r,val,x,y,gc;
        scanf("%ld",&n);
        n=n*2;
        mem(tree,-1);
        st.clear();
        for(int i=1; i<=n/2; i++)
        {
            scanf("%ld %ld",&l,&r);
            qq(1,n,l,r,1,i);
        }
        q(1,n,1);
        printf("Case %ld: ",k);
        printf("%ld\n",st.size());
    }
    return 0;
}