Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

为啥MLE啊,各位acmer大佬来康康,救救孩子,卡一晚上了

Posted by nbucty at 2020-02-12 21:16:32 on Problem 2528
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator