| ||||||||||
| 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 | |||||||||
为啥MLE啊,各位acmer大佬来康康,救救孩子,卡一晚上了#include<iostream>
#include<algorithm>
#include<vector>
#include<cstdio>
#include<string>
#include<cstring>
using namespace std;
typedef long long ll;
const int N=10223;
struct node{
int l,r;
int val;
int lazy;
}tr[N*8];
struct q{
int l,r;
}q[N];
int ans[N];
void pushup(int u){
if(!tr[u<<1].val||!tr[u<<1|1].val||tr[u<<1].val!=tr[u<<1|1].val)
tr[u].val=0;
else
tr[u].val=tr[u<<1].val;
}
void pushdown(int u){
if(tr[u].lazy){
tr[u<<1].val=tr[u<<1|1].val=tr[u].val;
tr[u<<1].lazy=tr[u<<1|1].lazy=tr[u].lazy;
tr[u].lazy=0;
}
}
void build(int u,int l,int r){
if(l==r){
tr[u].l=tr[u].r=l;
tr[u].val=-1;
tr[u].lazy=0;
}
else{
tr[u].l=l;
tr[u].r=r;
tr[u].val=-1;
tr[u].lazy=0;
int mid=l+r>>1;
build(u<<1,l,mid);
build(u<<1|1,mid+1,r);
}
}
void modify(int u,int l,int r,int x){
if(tr[u].l>=l&&tr[u].r<=r){
tr[u].val=x;
tr[u].lazy=x;
}
else{
pushdown(u);
int mid=tr[u].l+tr[u].r>>1;
if(l<=mid)
modify(u<<1,l,r,x);
if(r>mid)
modify(u<<1|1,l,r,x);
pushup(u);
}
}
vector<int> num;
int find(int x){
return lower_bound(num.begin(),num.end(),x)-num.begin()+1;
}
void query(int u,int l,int r){
if(tr[u].val==-1)
return ;
else if(tr[u].val){
ans[tr[u].val]++;
return ;
}
else{
pushdown(u);
int mid=tr[u].l+tr[u].r>>1;
query(u<<1,l,r);
query(u<<1|1,l,r);
return ;
}
}
int main(){
int t;
cin>>t;
while(t--){
int n;
memset(ans,0,sizeof ans);
cin>>n;
int i;
num.clear();
for(i=1;i<=n;i++){
scanf("%d%d",&q[i].l,&q[i].r);
num.push_back(q[i].l);
num.push_back(q[i].r);
}
sort(num.begin(),num.end());
num.erase(unique(num.begin(),num.end()),num.end());
for(i=0;i<(int)num.size()-1;i++){
if(num[i+1]-num[i]>1)
num.push_back(num[i+1]-1);
}
sort(num.begin(),num.end());
int size=num.size();
build(1,1,size);
for(i=1;i<=n;i++){
int l=find(q[i].l);
int r=find(q[i].r);
modify(1,l,r,i);
}
query(1,1,size);
int res=0;
for(i=1;i<=n;i++)
if(ans[i])
res++;
cout<<res<<endl;
}
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator