QOJ.ac

QOJ

ID提交记录ID题目HackerOwner结果提交时间测评时间
#786#530481#8035. Call Me Call Mehhy0613hhy0613Success!2024-08-24 17:49:022024-08-24 17:49:06

詳細信息

Extra Test:

Wrong Answer
time: 12ms
memory: 87628kb

input:

2
1 1 0
1 1 1

output:

1

result:

wrong answer 1st numbers differ - expected: '2', found: '1'

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#530481#8035. Call Me Call Mehhy0613WA 5575ms150064kbC++144.7kb2024-08-24 16:22:552024-08-24 18:00:13

answer

#include<bits/stdc++.h>
using namespace std;
const int N=400005,INF=0x3f3f3f3f;
int l[N],r[N],c[N],nodeL[N],nodeR[N],n;
bool xing[N];
vector<int> vec[N<<2],qe;
bool vis[N];
struct AAA{
	int val,pos;
	bool operator<(const AAA& aa)const{return (val<aa.val || (val==aa.val && pos<aa.pos));}
};
vector<AAA> vev[N<<2];
namespace seg{
	struct node{
		node *left,*right;
		int mn,add;
	}pool[N*40];
	int cnt;
	node* New(int x){
		pool[cnt]=node{nullptr,nullptr,x,0};
		return pool+(cnt++);
	}
	void sol(node* p){p->mn=min(p->left->mn,p->right->mn);}
	void add_add(node* p,int x){
		if(p==nullptr) return;
		p->mn+=x;
		p->add+=x;
	} 
	void push_down(node* p){
		if(p==nullptr || p->add==0) return;
		add_add(p->left,p->add);
		add_add(p->right,p->add);
		p->add=0;
	}
	node* build(const vector<int>& vec,int l,int r){
		if(l==r) return nullptr;
		if(l+1==r) return New(vec[l]);
		int mid=l+(r-l)/2;
		node* p=New(0);
		p->left=build(vec,l,mid);
		p->right=build(vec,mid,r);
		sol(p);
		return p;
	}
	void update(node* p,int l,int r,int pos,int x){
		if(l+1==r){
			p->mn=x;
			return;
		}
		push_down(p);
		int mid=l+(r-l)/2;
		if(pos<mid) update(p->left,l,mid,pos,x);
		else update(p->right,mid,r,pos,x);
		sol(p);
	}
	int query(node* p,int l,int r,int pos){
		if(l+1==r) return p->mn;
		push_down(p);
		int mid=l+(r-l)/2;
		if(pos<mid) return query(p->left,l,mid,pos);
		return query(p->right,mid,r,pos);
	}
	void add(node* p,int L,int R,int l,int r,int x){
		if(p==nullptr || l>=r) return;
		if(l<=L && R<=r){
			add_add(p,x);
			return;
		}
		push_down(p);
		int mid=L+(R-L)/2;
		if(l<mid) add(p->left,L,mid,l,r,x);
		if(r>mid) add(p->right,mid,R,l,r,x);
		sol(p);
	}
	void find0(node* p,int l,int r,vector<int>& vec){
		if(p==nullptr || p->mn>0) return;
		if(l+1==r){
			vec.push_back(l);
			return;
		}
		push_down(p);
		int mid=l+(r-l)/2;
		find0(p->left,l,mid,vec);
		find0(p->right,mid,r,vec); 
	}
}
seg::node* root[N<<2];
void solve(int p){
	if(root[p]==nullptr) return;
	vector<int> vec;
	seg::find0(root[p],0,(int)vev[p].size(),vec);
	for(int ii:vec){
		const int pos=vev[p][ii].pos;
		if(vis[pos]) continue;
		vis[pos]=true;
		const int i=nodeL[pos],j=nodeR[pos];
		const int v1=seg::query(root[p],0,(int)vev[p].size(),i),v2=seg::query(root[p],0,(int)vev[p].size(),j);
		assert(v1>=0 && v2>=0 && (v1==0 || v2==0));
		const int now=(v1+v2-(c[pos]&1));
		c[pos]=now;
		if(now==0){
			qe.push_back(pos);
			seg::update(root[p],0,(int)vev[p].size(),i,INF);
			seg::update(root[p],0,(int)vev[p].size(),j,INF);
		}else{
			seg::update(root[p],0,(int)vev[p].size(),i,(now+1)/2);
			seg::update(root[p],0,(int)vev[p].size(),j,(now+1)/2);
		}
	}
	for(int i:vec) vis[vev[p][i].pos]=false;
}
void build(int p,int L,int R){
	vev[p].clear();
	for(int i:vec[p]){
		vev[p].push_back(AAA{l[i],i});
		vev[p].push_back(AAA{r[i],i});
	}
	sort(vev[p].begin(),vev[p].end());
	for(int i=0;i<(int)vev[p].size();++i){
		if(l[vev[p][i].pos]==vev[p][i].val) nodeL[vev[p][i].pos]=i;
		else nodeR[vev[p][i].pos]=i;
	}
	vector<int> data;
	for(int i=0;i<(int)vev[p].size();++i){
		if(L+1==R) data.push_back(c[vev[p][i].pos]);
		else data.push_back((c[vev[p][i].pos]+1)/2);
	}
	root[p]=seg::build(data,0,(int)data.size());
	solve(p);
	if(L+1==R) return;
	int mid=L+(R-L)/2;
	build(p*2+1,L,mid);
	build(p*2+2,mid,R);
}
void update(int x){
	int p=0,L=0,R=n;
	while(true){
		int mid=L+(R-L)/2;
		const int pos=int(upper_bound(vev[p].begin(),vev[p].end(),AAA{x,INF})-vev[p].begin());
		if(L+1==R){
			seg::add(root[p],0,(int)vev[p].size(),int(lower_bound(vev[p].begin(),vev[p].end(),AAA{x,-INF})-vev[p].begin()),pos,-1);
			return;
		}
		if(x<mid){
			seg::add(root[p],0,(int)vev[p].size(),0,pos,-1);
			solve(p);
		}else{
			seg::add(root[p],0,(int)vev[p].size(),pos,(int)vev[p].size(),-1);
			solve(p);
		}
		if(x<mid){
			p=2*p+1;
			R=mid;
		}else{
			p=2*p+2;
			L=mid;
		}
	}
}
int main(){
	ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
	int T=1;
	while(T--){
		cin >> n;
		for(int i=0;i<n;++i){
			cin >> l[i] >> r[i] >> c[i];
			--l[i];
		}
		seg::cnt=0;
		for(int i=0;i<4*n;++i) vec[i].clear();
		for(int i=0;i<n;++i){
			int p=0,L=0,R=n;
			while(true){
				int mid=L+(R-L)/2;
				if(l[i]<=mid && mid<r[i]){
					vec[p].push_back(i);
					break;
				}
				if(r[i]<=mid){
					p=2*p+1;
					R=mid;
				}else{
					p=2*p+2;
					L=mid;
				}
			}
		}
		qe.clear();
		int start=0;
		build(0,0,n);
		for(int i=0;i<n;++i) xing[i]=false;
		while(start<(int)qe.size()){
			const int u=qe[start++];
			update(u);
			xing[u]=true;
		}
		int ans=0;
		for(int i=0;i<n;++i) ans+=xing[i];
		cout << ans << '\n';
	}
	return 0;
}