Submission #1313445

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313445		salmon	Sweeping (JOI20_sweeping)	C++20	0 / 100	1027 ms	596728 KiB

sweeping

#include <bits/stdc++.h>
using namespace std;

int N;
int M;
int Q;
int X[500100];
int Y[500100];

vector<int> de;
vector<int> dust;
int cont = 0;

int px[500100];
int py[500100];
vector<int> sise;
vector<set<int>> children;

vector<vector<int>> queries;

struct node{

	int x,y;
	pair<int,int> m;
	node *l,*r;
	
	set<pair<int,int>> satx;
	set<pair<int,int>> saty;
	
	node(int S, int E){
		x = S;
		y = E;
		m = {(x + N - y)/2, N - (x + N - y)/2};
		
		if(m.first != x) l = new node(x,m.second + 1);
		else l = NULL;
		
		if(m.second != y) r = new node(m.first + 1,y);
		else r = NULL;
	}
	
	void move(int X, int Y, int i){
		//printf("\n%d %d\n",x,y);
		if(X <= m.first && Y <= m.second){
			//printf("myballs\n");
			auto it = satx.lower_bound({X,-1});
			//printf("yourballs");
			if(it == satx.end() || it -> first != X){
				sise.push_back(X);
				satx.insert({X,cont});
				children.push_back({i});
				px[i] = cont;
				cont++;
			}
			else{
				//printf("f: %d\n",it->second);
				children[it -> second].insert(i);
				px[i] = it -> second;
			}
			//printf("done");
			it = saty.lower_bound({Y,-1});
			
			if(it == saty.end() || it -> first != Y){
				sise.push_back(Y);
				saty.insert({Y,cont});
				children.push_back({i});
				py[i] = cont;
				cont++;
			}
			else{
				//printf("y: %d",it->second);
				children[it -> second].insert(i);
				py[i] = it -> second;
			}
			return;
		}
		
		if(X > m.first){
			r -> move(X,Y,i);
			//printf("balls");
		}
		else if(Y > m.second){
			l -> move(X,Y,i);
			//printf("ohballs"); 
		}
		else{
			assert (1 == 2);
		}
		return;
	}
	
	void sweep(int L, bool isX){
		if(isX){
			if(L >= m.second){
				if(L > m.second) l -> sweep(L,isX);
				
				int pos = N - L;
				
				if(satx.size() != 0){
					pair<int,int> big = {-1,-1};
					vector<int> v;
					
					while(!satx.empty() && satx.begin() -> first <= pos){
						int it = satx.begin() -> second;
						satx.erase(satx.begin());
						big = max(big,{children[it].size(),it});
						v.push_back(it);
					}
					
					if(v.size() == 0) return;
					
					int it = big.second;
					
					for(int i : v){
						if(i == it) continue;
						
						for(int j : children[i]){
							px[j] = it;
							children[it].insert(j);
						}
						
						
						children[i].clear();
					}
					
					sise[it] = pos;
					satx.insert({pos,it});
				}
			}
			else if(L < m.second){
				r -> sweep(L,isX);
				
				while(!saty.empty() && saty.begin() -> first <= L){
					int it = saty.begin() -> second;
					saty.erase(saty.begin());
					
					while(!children[it].empty()){
						int i = *children[it].begin();
						children[it].erase(i);
						
						children[px[i]].erase(i);
						move(N-L,sise[it],i);
					}
				}
			}
			
		}
		else{
			
			if(L >= m.first){
				if(L > m.first) r -> sweep(L,isX);
				
				int pos = N - L;
				
				if(saty.size() != 0){
					pair<int,int> big = {-1,-1};
					vector<int> v;
					
					while(!saty.empty() && saty.begin() -> first <= pos){
						int it = saty.begin() -> second;
						saty.erase(saty.begin());
						big = max(big,{children[it].size(),it});
						v.push_back(it);
					}
					
					if(v.size() == 0) return;
					
					int it = big.second;
					
					for(int i : v){
						if(i == it) continue;
						
						for(int j : children[i]){
							py[j] = it;
							children[it].insert(j);
						}
						
						
						children[i].clear();
					}
					
					sise[it] = pos;
					saty.insert({pos,it});
				}
			}
			else if(L < m.first){
				l -> sweep(L,isX);
				
				while(!satx.empty() && satx.begin() -> first <= L){
					int it = satx.begin() -> second;
					saty.erase(satx.begin());
					
					while(!children[it].empty()){
						int i = *children[it].begin();
						children[it].erase(i);
						
						children[py[i]].erase(i);
						move(sise[it],N-L,i);
					}
				}
			}
			
		}
	}
	
}*root;

int invde(int x){
	return lower_bound(de.begin(),de.end(),x) - de.begin();
}

int main(){
	
	scanf(" %d",&N);
	scanf(" %d",&M);
	scanf(" %d",&Q);
	
	for(int i = 1; i <= M; i++){
		scanf(" %d",&X[i]);
		scanf(" %d",&Y[i]);
	}
	
	for(int i = 0; i < Q; i++){
		int T;
		int h;
		scanf(" %d",&T);
		
		if(T == 1){
			scanf(" %d",&h);
			
			queries.push_back({T,h});
		}
		else if(T == 2){
			scanf(" %d",&h);
			
			queries.push_back({T,h});
		}
		else if(T == 3){
			scanf(" %d",&h);
		
			queries.push_back({T,h});
		}
	}
	
	for(int i = 1; i <= M; i++){
		de.push_back(X[i]);
		de.push_back(Y[i]);
	}
	
	for(int i = 0; i < Q; i++){
		if(queries[i][0] == 2 || queries[i][0] == 3){
			de.push_back(queries[i][1]);
		}
	}
	
	int temp = de.size();
	for(int i = 0; i < temp; i++){
		de.push_back(N - de[i]);
	}
	
	sort(de.begin(),de.end());
	de.resize(unique(de.begin(),de.end()) - de.begin());
	
	for(int i = 1; i <= M; i++){
		X[i] = invde(X[i]);
		Y[i] = invde(Y[i]);
	}
	
	for(int i = 0; i < Q; i++){
		if(queries[i][0] == 2 || queries[i][0] == 3){
			queries[i][1] = invde(queries[i][1]);
		}
	}
	N = de.size() - 1;

	root = new node(0,0);

	for(int i = 1; i <= M; i++){
		root -> move(X[i],Y[i],i);
	}

	for(int i = 0; i < Q; i++){
		//printf("%d\n",i);
		if(queries[i][0] == 1){
			int it = queries[i][1];
			printf("%d %d\n",de[sise[px[it]]],de[sise[py[it]]]);
		}
		else if(queries[i][0] == 2){
			root -> sweep(queries[i][1],true);
		}
		else if(queries[i][0] == 3){
			root -> sweep(queries[i][1],false);
		}
	}
	
}

Compilation message (stderr)

sweeping.cpp: In function 'int main()':
sweeping.cpp:214:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  214 |         scanf(" %d",&N);
      |         ~~~~~^~~~~~~~~~
sweeping.cpp:215:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  215 |         scanf(" %d",&M);
      |         ~~~~~^~~~~~~~~~
sweeping.cpp:216:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  216 |         scanf(" %d",&Q);
      |         ~~~~~^~~~~~~~~~
sweeping.cpp:219:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  219 |                 scanf(" %d",&X[i]);
      |                 ~~~~~^~~~~~~~~~~~~
sweeping.cpp:220:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  220 |                 scanf(" %d",&Y[i]);
      |                 ~~~~~^~~~~~~~~~~~~
sweeping.cpp:226:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  226 |                 scanf(" %d",&T);
      |                 ~~~~~^~~~~~~~~~
sweeping.cpp:229:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  229 |                         scanf(" %d",&h);
      |                         ~~~~~^~~~~~~~~~
sweeping.cpp:234:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  234 |                         scanf(" %d",&h);
      |                         ~~~~~^~~~~~~~~~
sweeping.cpp:239:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  239 |                         scanf(" %d",&h);
      |                         ~~~~~^~~~~~~~~~

• Subtask 1: 0 / 1
• Subtask 2: 0 / 10
• Subtask 3: 0 / 11
• Subtask 4: 0 / 53
• Subtask 5: 0 / 25