Submission #1356344

#TimeUsernameProblemLanguageResultExecution timeMemory
1356344silence25Magija (COCI26_magija)C++20
73 / 110
1096 ms4908 KiB
#include "bits/stdc++.h"
#define ff first
#define ss second
#define pp pop_back
#define ll long long
#define pb emplace_back
#define pq priority_queue
#define ls(v) (int)v.size()
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define mnpq(asd) asd,vector<asd>,greater<asd>
#define fe(a,b,i) for(int i = a;i<=b;++i)
#define ef(a,b,i) for(int i = a;i>=b;--i)
#define pii pair<int,int>
#define wr cout << "------------------------" << endl

using namespace std;

const int N = 2e5 + 5;
int mx[N];
int mn[N];
int par[N];
int lens[N];

int find(int x){
	if(x == par[x])
		return x;
	return par[x] = find(par[x]);
}

bool merge(int x,int y){
	if((x = find(x)) == (y = find(y)))
		return false;
	if(lens[x] < lens[y])
		swap(x,y);
	lens[x] += lens[y];
	par[y] = x;
	mx[x] = max(mx[x],mx[y]);
	mn[x] = min(mn[x],mn[y]);
	return true;
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);
    int n,q;
    cin >> n >> q;
    for(int i = 1;i<=n;++i){
    	mx[i] = mn[i] = par[i] = i;
    	lens[i] = 1;
    }

    while(q--){
    	int tp;
    	cin >> tp;
    	if(tp == 1){
    		int x;
    		cin >> x;
    		x = find(x);
    		cout << mn[x] << ' ' << mx[x] << endl;
    	}
    	else{
	    	int l,r,val;
	    	cin >> l >> r >> val;
	    	vector<int>a,b;
	    	for(int i = l;i<= l + val - 1;++i)
	    		a.pb(i);
	    	for(int i = r;i<= r + val - 1;++i)
	    		b.pb(i);
	    	for(int i = 0;i<ls(a);++i)
	    		merge(a[i],b[i]);
    	}
    }

    return 0;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...