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