Submission #17136359

---

Source Code Expand

#include <iostream>
#include <vector>
using i64 = long long;

int main() {
    int n;
    std::cin >> n;
    std::vector<std::pair<int, int>> v(n);
    for (int i = 0; i < n; i++) {
        int x, y;
        std::cin >> x >> y;
        --x; --y;
        v[x].first = y;
        v[x].second = i;
    }

    std::vector<int> comp(n), used(n);
    int s = 0, t = 0;
    for (int i = 0; i < n; i++) {
        const int y = v[i].first;
        comp[i] = t;
        used[y] = 1;
        if (y > n - 1 - i) s++;
        if (used[n - 1 - i]) s++;
        if (s == i + 1) t++;
    }

    std::vector<int> ret(n);
    for (int i = 0; i < n;) {
        int j = i + 1;
        while (j < n && comp[j] == comp[i]) j++;
        const int r = j - i;
        while (i < j) ret[v[i++].second] = r;
    }

    for (const int r : ret) std::cout << r << '\n';

    return 0;
}

Submission Info

Judge Result