সি++ প্রোগ্রাম: প্রতিটি সিটি থেকে ভিজিট করা যেতে পারে এমন সিটির সংখ্যা গণনা

Nটি কোঅর্ডিনেট পয়েন্ট P দেওয়া আছে (xi, yi) ফর্মে। x ও y মানগুলো প্রথম N প্রাকৃতিক সংখ্যার পারমুটেশন। প্রতিটি k (1 থেকে N) এর জন্য আমরা সিটি k-তে আছি। আমরা আর্বিট্রেরিলি অপারেশন অ্যাপ্লাই করতে পারি। অপারেশন: আমরা অন্য একটি সিটিতে যেতে পারি যেটির x-কোঅর্ডিনেট ও y-কোঅর্ডিনেট উভয়ই বর্তমান সিটির চেয়ে ছোট, অথবা উভয়ই বড়। প্রতিটি সিটি k থেকে কতগুলো সিটি পৌঁছানো যায় সেটি বের করতে হবে।

ইনপুট P = [[1,4],[2,3],[3,1],[4,2]] হলে আউটপুট [1,1,2,2]

পদ্ধতি (Steps)

n := P-এর সাইজ
2D অ্যারে lst ডিক্লেয়ার
i=0 থেকে n-1 পর্যন্ত লুপ:
    v := { P[i][0], P[i][1], i }
    lst-এ v পুশ করুন
lst সর্ট করুন
y_min := 1e9
সেট se ডিক্লেয়ার
ans অ্যারে সাইজ n, ০ দিয়ে ফিল
i=0 থেকে n-1 পর্যন্ত লুপ:
    y_min := min(y_min, lst[i][1])
    se-তে lst[i][2] ইনসার্ট করুন
    যদি y_min + i == n হয়, তবে
        se-র প্রতিটি j এর জন্য ans[j] := se.size()
        se ক্লিয়ার করুন
    যদি i == n-1 হয়, তবে
        se-র প্রতিটি j এর জন্য ans[j] := se.size()
i=0 থেকে n-1 পর্যন্ত ans[i] প্রিন্ট করুন

উদাহরণ কোড (C++)

#include <bits/stdc++.h>
using namespace std;
void solve(vector<vector<int>> P) {
    int n = P.size();
    vector<vector<int>> lst;
    for (int i = 0; i < n; i++) {
        vector<int> v = { P[i][0], P[i][1], i };
        lst.push_back(v);
    }
    sort(lst.begin(), lst.end());
    int y_min = 1e9;
    set<int> se;
    vector<int> ans(n, 0);
    for (int i = 0; i < n; i++) {
        y_min = min(y_min, lst[i][1]);
        se.insert(lst[i][2]);
        if (y_min + i == n) {
            for (auto j : se) ans[j] = se.size();
            se.clear();
        }
        if (i == n - 1) {
            for (auto j : se) ans[j] = se.size();
        }
    }
    for (int i = 0; i < n; i++) {
        cout << ans[i] << ", ";
    }
}
int main() {
    vector<vector<int>> P = { {1,4}, {2,3}, {3,1}, {4,2} };
    solve(P);
}

ইনপুট

{ {1,4}, {2,3}, {3,1}, {4,2} }

আউটপুট

1, 1, 2, 2,