Submission #1007838

#	Time	Username	Problem	Language	Result	Execution time	Memory
1007838		amirhoseinfar1385	Vinjete (COI22_vinjete)	C++17	100 / 100	886 ms	484260 KiB

Main

#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10;
struct yal{
	int u,v,l,r;
	int getad(int fu){
		return (fu^u^v);
	}
}alle[maxn];
vector<int>adj[maxn];
int n,m,kaf=(1<<30),res[maxn];
struct node{
	int mina,lazy,ted,cl,cr,l,r;
	node(){
		mina=lazy=ted=0;
		cl=cr=-1;
	}
}fakenode;

struct segment{
	vector<node>seg;
	segment(){
		seg.resize(2);
		seg[1].l=0;
		seg[1].r=kaf-1;
		seg[1].ted=kaf;
	}
	int getl(int i){
		if(seg[i].cl==-1){
			seg.push_back(fakenode);
			seg[i].cl=(int)seg.size()-1;
			seg.back().l=seg[i].l;
			seg.back().r=(seg[i].l+seg[i].r)/2;
			seg.back().ted=seg.back().r-seg.back().l+1;
		}
		return seg[i].cl;
	}
	int getr(int i){
		if(seg[i].cr==-1){
			seg.push_back(fakenode);
			seg[i].cr=(int)seg.size()-1;
			seg.back().l=(seg[i].l+seg[i].r)/2+1;
			seg.back().r=seg[i].r;
			seg.back().ted=seg.back().r-seg.back().l+1;
		}
		return seg[i].cr;
	}
	node comp(node a,node b){
		if(a.mina<b.mina){
			return a;
		}
		if(b.mina<a.mina){
			return b;
		}
		b.ted+=a.ted;
		return b;
	}
	void calc(int i){
		if(seg[i].l==seg[i].r){
			seg[i].mina+=seg[i].lazy;
			seg[i].lazy=0;
			return ;
		}
		auto x=comp(seg[getl(i)],seg[getr(i)]);
		seg[i].mina=x.mina;
		seg[i].ted=x.ted;
		seg[i].mina+=seg[i].lazy;
	}
	void shift(int i){
		if(seg[i].l==seg[i].r){
			return ;
		}
		seg[getl(i)].lazy+=seg[i].lazy;
		seg[getr(i)].lazy+=seg[i].lazy;
		calc(getl(i));
		calc(getr(i));
		seg[i].lazy=0;
		return ;
	}
	void add(int i,int l,int r,int tl,int tr,int w){
		if(l>r||l>tr||r<tl||tl>tr){
			return ;
		}
		if(l>=tl&&r<=tr){
			seg[i].lazy+=w;
			calc(i);
			//cout<<"wtf: "<<seg[i].lazy<<" "<<seg[i].mina<<" "<<i<<" "<<l<<" "<<r<<endl;
			return ;
		}
		shift(i);
		int m=(l+r)>>1;
		add(getl(i),l,m,tl,tr,w);
		add(getr(i),m+1,r,tl,tr,w);
		calc(i);
	}
	node pors(int i,int l,int r,int tl,int tr){
		if(l>r||l>tr||r<tl||tl>tr){
			node fk;
			fk.mina=maxn+10;
			return fk;
		}
		shift(i);
		calc(i);
		if(l>=tl&&r<=tr){
			//cout<<l<<" "<<r<<" "<<seg[i].mina<<" "<<seg[i].ted<<" "<<seg[i].lazy<<endl;
			return seg[i];
		}
		int m=(l+r)>>1;
		return comp(pors(getl(i),l,m,tl,tr),pors(getr(i),m+1,r,tl,tr));
	}
}seg;

void vorod(){
	cin>>n>>m;
	for(int i=0;i<n;i++){
		cin>>alle[i].u>>alle[i].v>>alle[i].l>>alle[i].r;
		adj[alle[i].u].push_back(i);
		adj[alle[i].v].push_back(i);
	}
}

void dfssolve(int u,int par=-1){
	node a=seg.pors(1,0,kaf-1,1,m);
	//cout<<u<<" "<<a.mina<<endl;
	if(a.mina!=0){
		a.ted=0;
	}
	res[u]=a.ted;
	for(auto x:adj[u]){
		int v=alle[x].getad(u);
		if(v==par){
			continue;
		}
		seg.add(1,0,kaf-1,alle[x].l,alle[x].r,1);
		dfssolve(v,u);
		seg.add(1,0,kaf-1,alle[x].l,alle[x].r,-1);
	}
}

void solve(){
	dfssolve(1);	
}

void khor(){
	for(int i=2;i<=n;i++){
		res[i]=m-res[i];
		cout<<res[i]<<"\n";
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	//cout.tie(0);
	//freopen("inp.txt","r",stdin);
	vorod();
	solve();
	khor();
}

• Subtask 1: 11 / 11
• Subtask 2: 13 / 13
• Subtask 3: 16 / 16
• Subtask 4: 29 / 29
• Subtask 5: 31 / 31