oj.uz

Submission #916989

# Submission time Handle Problem Language Result Execution time Memory
916989 2024-01-26T22:56:44 Z MilosMilutinovic Sweeping (JOI20_sweeping) C++14
65 / 100
 7248 ms 607636 KB 
#include<bits/stdc++.h>
 
#define pb push_back
#define fi first
#define se second
#define mp make_pair
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
 
template <typename T> bool chkmin(T &x,T y){return x>y?x=y,1:0;}
template <typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;}
 
ll readint(){
	ll x=0,f=1; char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}

int n,m,q;
int v[1500005][2],fa[1500005],ch[1500005][2],tag[1500005][2],prior[1500005];
mt19937 rng(time(0));
 
void make(int id){ tag[id][0]=tag[id][1]=-1; prior[id]=rng(); fa[id]=ch[id][0]=ch[id][1]=0; }
 
void pushdown(int id){
	if(!id) return;
	for(int i=0;i<2;i++){
		if(tag[id][i]==-1) continue;
		for(int j=0;j<2;j++){
			if(ch[id][j]==0) continue;
			v[ch[id][j]][i]=tag[id][i];
			tag[ch[id][j]][i]=tag[id][i];
		}
		tag[id][i]=-1;
	}
}
 
void split(int id,int&l,int&r,int a,int b,int idx){
	if(!id) return (void)(l=r=0);
	pushdown(id);
	if(v[id][0]<=a&&v[id][1]<=b&&(mp(v[id][0],v[id][1])!=mp(a,b)||id<idx)){
		fa[ch[id][1]]=0;
		split(ch[id][1],ch[id][1],r,a,b,idx);
		l=id; 
		fa[ch[id][1]]=id;
	}else{
		fa[ch[id][0]]=0;
		split(ch[id][0],l,ch[id][0],a,b,idx);
		r=id;  
		fa[ch[id][0]]=id;
	}
}
 
void merge(int&id,int l,int r){
	if(!l) return (void)(id=r);
	if(!r) return (void)(id=l);
	pushdown(l);
	pushdown(r);
	if(prior[l]>prior[r]) swap(l,r);
	int L=0,R=0;
	split(l,L,R,v[r][0],v[r][1],r);
	fa[ch[r][0]]=0;
	fa[ch[r][1]]=0;
	merge(ch[r][0],ch[r][0],L);
	merge(ch[r][1],ch[r][1],R);
	fa[ch[r][0]]=r;
	fa[ch[r][1]]=r;
	id=r;
	pushdown(id);
}

namespace segtree{
	int root,tsz,ls[10000005],rs[10000005];
	map<int,multiset<pii>> ids;
	pii mini[10000005];
	void modify(int&id,int l,int r,int i,pii v){
		if(!id) id=++tsz,mini[id]=mp(n+1,0);
		if(l==r) return (void)(mini[id]=v);
		int mid=(l+r)/2;
		if(i<=mid) modify(ls[id],l,mid,i,v);
		else modify(rs[id],mid+1,r,i,v);
		mini[id]=mp(n+1,0);
		if(ls[id]) mini[id]=min(mini[id],mini[ls[id]]);
		if(rs[id]) mini[id]=min(mini[id],mini[rs[id]]);
	}
	pii query(int id,int l,int r,int ql,int qr){
		if(!id||l>r||l>qr||r<ql) return mp(n+1,0);
		if(ql<=l&&r<=qr) return mini[id];
		int mid=(l+r)/2;
		return min(query(ls[id],l,mid,ql,qr),query(rs[id],mid+1,r,ql,qr));
	}
	void add(int x,int y,int i){
		ids[x].emplace(y,i);
		modify(root,0,n,x,*ids[x].begin());
	}
	void rem(int x,int y,int i){
		if(ids[x].find(mp(y,i))==ids[x].end()) while(true){}
		ids[x].erase(ids[x].find(mp(y,i)));
		modify(root,0,n,x,(ids[x].empty()?mp(n+1,0):*ids[x].begin()));
	}
	pii get(int l,int r){ return query(root,0,n,l,r); }
};

vector<int> find(int l){
	vector<int> ret;
	while(true){
		pii mn=segtree::get(0,l);
		if(mn.fi>n-l) break;
		int i=mn.se;
		segtree::rem(v[i][0],v[i][1],i);
		while(fa[i]) i=fa[i];
		ret.pb(i);
	}
	return ret;
}

int godown(int id){
	if(!ch[id][0]) return id;
	else return godown(ch[id][0]);
}
 
int main(){
	n=readint();
	m=readint();
	q=readint();
	for(int i=1;i<=m;i++) for(int j=0;j<2;j++) v[i][j]=readint();
	for(int i=1;i<=m;i++) make(i),segtree::add(v[i][0],v[i][1],i);
	while(q--){
		int t=readint();
		if(t==1){
			int i=readint();
			vector<int> anc;
			for(int v=i;v;v=fa[v]) anc.pb(v);
			reverse(anc.begin(),anc.end());
			for(int v:anc) pushdown(v);
			printf("%d %d\n",v[i][0],v[i][1]);
		}
		if(t==2){
			int l=readint();
			int root=0;
			vector<int> ids=find(n-l);
			for(int i:ids){
				int L=0,R=0;
				split(i,L,R,n-l,l,1e9);
				if(R!=0){
					int x=godown(R);
					vector<int> anc;
					for(int v=x;v;v=fa[v]) anc.pb(v);
					reverse(anc.begin(),anc.end());
					for(int v:anc) pushdown(v);
					segtree::add(v[x][0],v[x][1],x);
				}
				v[L][0]=n-l;
				tag[L][0]=n-l;
				pushdown(L);
				merge(root,root,L);
				pushdown(root);
			}
			if(root!=0){
				int x=godown(root);
				vector<int> anc;
				for(int v=x;v;v=fa[v]) anc.pb(v);
				reverse(anc.begin(),anc.end());
				for(int v:anc) pushdown(v);
				segtree::add(v[x][0],v[x][1],x);
			}
		}
		if(t==3){
			int l=readint();
			int root=0;
			vector<int> ids=find(l);
			for(int i:ids){
				int L=0,R=0;
				split(i,L,R,l,n-l,1e9);				
				if(R!=0){
					int x=godown(R);
					vector<int> anc;
					for(int v=x;v;v=fa[v]) anc.pb(v);
					reverse(anc.begin(),anc.end());
					for(int v:anc) pushdown(v);
					segtree::add(v[x][0],v[x][1],x);
				}
				v[L][1]=n-l;
				tag[L][1]=n-l;
				pushdown(L);
				pushdown(R);
				merge(root,root,L);
				pushdown(root);
			}
			if(root!=0){
				int x=godown(root);
				vector<int> anc;
				for(int v=x;v;v=fa[v]) anc.pb(v);
				reverse(anc.begin(),anc.end());
				for(int v:anc) pushdown(v);
				segtree::add(v[x][0],v[x][1],x);
			}
		}
		if(t==4){
			make(++m);
			for(int j=0;j<2;j++) v[m][j]=readint();
			segtree::add(v[m][0],v[m][1],m);	
		}
	}
	return 0;
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 15452 KB Output is correct
2 Correct 9 ms 15196 KB Output is correct
3 Correct 6 ms 15480 KB Output is correct
4 Correct 13 ms 15708 KB Output is correct
5 Correct 12 ms 12892 KB Output is correct
6 Correct 5 ms 12788 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 7248 ms 607636 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2663 ms 228124 KB Output is correct
2 Correct 2299 ms 223420 KB Output is correct
3 Correct 1500 ms 237268 KB Output is correct
4 Correct 2842 ms 271172 KB Output is correct
5 Correct 2274 ms 220492 KB Output is correct
6 Correct 2066 ms 223104 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 2663 ms 228124 KB Output is correct
2 Correct 2299 ms 223420 KB Output is correct
3 Correct 1500 ms 237268 KB Output is correct
4 Correct 2842 ms 271172 KB Output is correct
5 Correct 2274 ms 220492 KB Output is correct
6 Correct 2066 ms 223104 KB Output is correct
7 Correct 5337 ms 245212 KB Output is correct
8 Correct 5155 ms 245592 KB Output is correct
9 Correct 5211 ms 245028 KB Output is correct
10 Correct 4030 ms 244304 KB Output is correct
11 Correct 7115 ms 271056 KB Output is correct
12 Correct 5364 ms 220688 KB Output is correct
13 Correct 5354 ms 224612 KB Output is correct
14 Correct 115 ms 16564 KB Output is correct
15 Correct 949 ms 87888 KB Output is correct
16 Correct 5293 ms 262384 KB Output is correct
17 Correct 4612 ms 243084 KB Output is correct

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 15452 KB Output is correct
2 Correct 9 ms 15196 KB Output is correct
3 Correct 6 ms 15480 KB Output is correct
4 Correct 13 ms 15708 KB Output is correct
5 Correct 12 ms 12892 KB Output is correct
6 Correct 5 ms 12788 KB Output is correct
7 Runtime error 7248 ms 607636 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -