Submission #1347340

#TimeUsernameProblemLanguageResultExecution timeMemory
1347340reivaxmarMagija (COCI26_magija)C++20
73 / 110
1095 ms7208 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pii pair<int, int>
#define mp make_pair
#define F first
#define S second
#define endl "\n"

#define vi vector<int>
#define vvi vector<vi>

struct DSU {
    vector<int> parent;
    vector<int> size;
    vector<int> mn;
    vector<int> mx;
    DSU(int n) : parent(n, -1), size(n, 1), mn(n, -1), mx(n, -1) {
        for(int i = 0; i < n; i++) {
            parent[i] = i;
            mn[i] = i;
            mx[i] = i;
        }
    }

    int Union(int a, int b) {
        a = Find(a);
        b = Find(b);
        if(a != b) {
            if(size[a] < size[b])
                swap(a, b);
            parent[b] = a;
            size[a] += size[b];
            mn[a] = min(mn[a], mn[b]);
            mn[b] = mn[a];
            mx[a] = max(mx[a], mx[b]);
            mx[b] = mx[a];
        }
        return a;
    }

    int Find(int v) {
        if(v == parent[v]) {
            return v;
        }
        return parent[v] = Find(parent[v]);
    }
};

void solve() {
    int n, q;
    cin >> n >> q;
    DSU dsu(n);
    while(q--) {
        int a;
        cin >> a;
        if(a == 1) {
            int x;
            cin >> x;
            int r = dsu.Find(x-1);
            cout << dsu.mn[r] + 1 << " " << dsu.mx[r] + 1 << endl;
        } else {
            int l, r, len;
            cin >> l >> r >> len;
            for(int i = 0; i < len; i++) {
                dsu.Union(l + i-1, r + i-1);
            }
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    // int t;
    // cin >> t;
    // while(t--) {
    //     solve();
    // }
    solve();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...