Submission

Score: 80

User: meme_boi2

Problemset: เธอ ๆ มันเรียงกันยังไงอะ

Language: cpp

Time: 0.002 second

Submitted On: 2025-09-02 21:31:55

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2502;
class Solution {
public:
    int n, sz=1,LIS = -1;
    int tree[2*MAXN];
    unordered_map<int,int> mp;
    int lengthOfLIS(vector<int>& nums) {
        n = nums.size();
        while(sz < n) sz*=2;
        vector <int> temp = nums;
        sort(temp.begin(),temp.end());
        temp.erase(unique(temp.begin(),temp.end()),temp.end());
        for(int i = 0; i < temp.size(); i++){
            mp[temp[i]] = i;
        }
        for(int i = 0; i < n; i++){
           // cout << query(0,mp[nums[i]]-1)+1 << '\n';
            update(mp[nums[i]],query(0,mp[nums[i]]-1)+1);
        }
        return LIS;
    }
    void update(int idx,int val){
        idx += sz;
        tree[idx] = val;
        LIS = max(LIS,val);
        idx /= 2;
        while(idx > 0){
            tree[idx] = max(tree[2*idx],tree[2*idx+1]);
            idx /= 2;
        }
    }
    int query(int l,int r){
        l += sz, r += sz;
        int ans = 0;
        while(l <= r){
            if(l%2 == 1){
                ans = max(tree[l],ans);
                l++;
            }
            if(r%2 == 0){
                ans = max(tree[r],ans);
                r--;
            }
            l/= 2;
            r/= 2;
        }
        return ans;
    }
};
int32_t main(){
    cin.tie(nullptr)->sync_with_stdio(0);
    Solution sol;
    int n; cin >> n;
    if(n==0) cout << "sorted!";
    vector<int> mat(n);
    for(auto &x: mat) cin >> x;
    if(sol.lengthOfLIS(mat) == n){
        cout << "sorted!";
    }else{
        cout << "un-sorted!";
    }
}