Submission #41075676

Source Code Expand

/**
 *   @FileName	a.cpp
 *   @Author	kanpurin
 *   @Created	2023.04.30 21:30:11
**/

#include "bits/stdc++.h" 
using namespace std; 
typedef long long ll;


template < class Monoid >
struct SegmentTree {
private:
    using Func = std::function< Monoid(Monoid, Monoid) >;
    Func F;
    Monoid UNITY;
    int n;
    std::vector< Monoid > node;

    int _binary_search(int a, int b, const std::function<bool(Monoid)> &f, Monoid &s, int k = 0, int l = 0, int r = -1) {
        if (r < 0) r = n;
        if (r <= a || b <= l) return n;
        if (a <= l && r <= b && !f(F(s,node[k]))) {
            s = F(s,node[k]);
            return n;
        }
        if (l == r - 1) {s = F(s,node[k]); return l;}
        int ret = _binary_search(a, b, f, s, 2 * k + 1, l, (r - l) / 2 + l);
        return ret != n ? ret : _binary_search(a, b, f, s, 2 * k + 2, (r - l) / 2 + l, r);
    }

public:
    SegmentTree() {}

    SegmentTree(const std::vector< Monoid > &v, const Func f, const Monoid &unity) {
        F = f;
        UNITY = unity;
        int sz = v.size();
        n = 1;
        while (n < sz) n <<= 1;
        node.resize(n * 2 - 1, UNITY);
        for (int i = 0; i < sz; i++) node[i + n - 1] = v[i];
        build();
    }

    SegmentTree(int m, const Monoid &val, const Func f, const Monoid &unity) {
        F = f;
        UNITY = unity;
        n = 1;
        while (n < m) n <<= 1;
        node.resize(n * 2 - 1, UNITY);
        if (val != UNITY) {
            for (int i = 0; i < m; i++) node[i + n - 1] = val;
            build();
        }
    }

    void set(int k, const Monoid &x) {
        node[n + k - 1] = x;
    }

    void build() {
        for (int i = n - 2; i >= 0; i--) node[i] = F(node[2 * i + 1], node[2 * i + 2]);
    }

    void update_query(int x, const Monoid &val) {
        if (x >= n || x < 0) return;
        x += n - 1;
        node[x] = val;
        while (x > 0) {
            x = (x - 1) >> 1;
            node[x] = F(node[2 * x + 1], node[2 * x + 2]);
        }
    }

    Monoid get_query(int l, int r) {
        Monoid L = UNITY, R = UNITY;
        if (l < 0) l = 0;
        if (r < 0) return UNITY;
        if (l >= n) return UNITY;
        if (r >= n) r = n;
        for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if (l & 1) L = F(L, node[l++ - 1]);
            if (r & 1) R = F(node[--r - 1], R);
        }
        return F(L, R);
    }

    int binary_search(int l, int r, const std::function<bool(Monoid)> &f) {
        Monoid s = UNITY;
        int ret = _binary_search(l,r,f,s);
        return ret != n ? ret : -1;
    }

    Monoid operator[](int x) const {
        return node[n + x - 1];
    }

    int size() {
        return n;
    }

    void print() {
        for (int i = 0; i < n; i++) {
            std::cout << i << "\t: " << node[n + i - 1] << std::endl;
        }
    }
};

template<typename T>
struct Myset {
private:
    struct node_t {
        node_t *ch[2]; int sz;
        T x;
        node_t(T x) {
            ch[0] = ch[1] = nullptr;
            sz = 1;
            this->x = x;
        }
    };

    node_t *tr; 

    int sz(node_t *n) { return (n==nullptr) ? 0 : n->sz; }
    int wei(node_t *n) { return sz(n)+1; }
    void update(node_t *n) {
        assert(n != nullptr);
        n->sz = 1 + sz(n->ch[0]) + sz(n->ch[1]);
    }
    node_t *rotate(node_t *n, int ty) {
        node_t *m = n->ch[ty];
        n->ch[ty] = m->ch[1-ty];
        m->ch[1-ty] = n;
        update(n); update(m);
        return m;
    }
    node_t *balance(node_t *n) {
        for (int f = 0; f <= 1; f++) {
            if (wei(n->ch[f])*2 > wei(n->ch[1-f])*5) {
                if (wei(n->ch[f]->ch[f])*3 < wei(n->ch[f]->ch[1-f])*2) {
                    n->ch[f] = rotate(n->ch[f], 1-f);
                }
                return rotate(n, f);
            }
        }
        return n;
    }
    node_t *_insert(node_t *n, T x) {
        if (n == nullptr) return new node_t(x);
        if (x <= n->x) {
            n->ch[0] = _insert(n->ch[0], x);
        } else {
            n->ch[1] = _insert(n->ch[1], x);
        }
        update(n);
        return balance(n);
    }
    T _at(node_t *n, int k) {
        assert(n != nullptr);
        assert(0 <= k && k < sz(n));
        if (k < sz(n->ch[0])) {
            return _at(n->ch[0], k);
        }
        if (k == sz(n->ch[0])) return n->x;
        return _at(n->ch[1], k - sz(n->ch[0]) - 1);
    }
    int _lower_bound(node_t *n, T x) {
        if (n == nullptr) return 0;
        if (x <= n->x) return _lower_bound(n->ch[0], x);
        return sz(n->ch[0]) + 1 + _lower_bound(n->ch[1], x);
    }
    int _upper_bound(node_t *n, T x) {
        if (n == nullptr) return 0;
        if (x < n->x) return _upper_bound(n->ch[0], x);
        return sz(n->ch[0]) + 1 + _upper_bound(n->ch[1], x);
    }
    node_t *_erase(node_t *n, int k) {
        if (k < sz(n->ch[0])) {
            n->ch[0] = _erase(n->ch[0], k);
        } else if (k > sz(n->ch[0])) {
            n->ch[1] = _erase(n->ch[1], k - sz(n->ch[0]) - 1);
        } else {
            if (n->ch[0] == nullptr) return n->ch[1];
            n->x = _at(n->ch[0], sz(n->ch[0])-1);
            n->ch[0] = _erase(n->ch[0], sz(n->ch[0]) - 1);
        }
        update(n);
        return balance(n);
    }
public:
    Myset() { this->tr = nullptr; }
    int size() { return sz(this->tr); }
    
    void insert(T x) { this->tr = _insert(this->tr, x); }

    void insert_unique(T x) { 
        int t = _lower_bound(this->tr, x);
        if (t < sz(this->tr)) this->tr = _insert(this->tr, x); 
    }
    
    T get_kth(int k) { return _at(this->tr,k); }

    T get_max() { return _at(this->tr,sz(this->tr)-1); }

    T get_min() { return _at(this->tr,0); }

    int lower_bound(T x) { return _lower_bound(this->tr,x); }

    int upper_bound(T x) { return _upper_bound(this->tr,x); }

    void erase_kth(int k) { this->tr = _erase(this->tr, k); }

    void erase(T x) {
        int t = _lower_bound(this->tr, x);
        if (t < sz(this->tr)) this->tr = _erase(this->tr, t); 
    }

    void erase_all(T x) {
        int t = _lower_bound(this->tr, x);
        while(t < sz(this->tr)) this->tr = _erase(this->tr, t); 
    }

    int count_less(T x) {
        return _upper_bound(this->tr, x);
    }    
    
    int count_more(T x) {
        return sz(this->tr) - _lower_bound(this->tr, x);
    }

    void print() {
        cout << "[ ";
        for (int i = 0; i < sz(this->tr); i++) {
            cout << _at(this->tr,i) << " ";
        }
        cout << "]" << endl;
    }
};

int main() {
    int n,m;cin >> n >> m;
    vector<int> a(n);
    vector<int> tail(m);
    vector<vector<int>> pos(m);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        a[i]--;
        tail[a[i]] = i;
        pos[a[i]].push_back(i);
    }
    Myset<int> st;
    for (int i = 0; i < m; i++) {
        st.insert(tail[i]);
    }
    using P = pair<int,int>;
    SegmentTree<P> seg(n,{m,n},[](P x,P y){return min(x,y);},{m,n});
    for (int i = 0; i < n; i++) {
        seg.set(i,{a[i],i});
    }
    seg.build();
    int p = 0;
    vector<int> ans;
    for (int i = 0; i < m; i++) {
        int q = st.get_min();
        P t = seg.get_query(p,q+1);
        p = t.second + 1;
        ans.push_back(t.first+1);
        for (int j = 0; j < pos[t.first].size(); j++) {
            seg.update_query(pos[t.first][j],{m,n});
        }
        st.erase(tail[t.first]);
    }
    for (int i = 0; i < m; i++) {
        cout << ans[i] << " ";
    }
    cout << endl;
    return 0;
}

Submission Info

Submission Time
Task G - Minimum Permutation
User kanpurin
Language C++ (GCC 9.2.1)
Score 600
Code Size 7800 Byte
Status AC
Exec Time 235 ms
Memory 27176 KiB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:270:27: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  270 |         for (int j = 0; j < pos[t.first].size(); j++) {
      |                         ~~^~~~~~~~~~~~~~~~~~~~~

Judge Result

Set Name Sample All AfterContest
Score / Max Score 0 / 0 600 / 600 0 / 0
Status
AC × 3
AC × 47
AC × 1
Set Name Test Cases
Sample 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt
All 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt, 01_max_03.txt, 01_max_04.txt, 01_max_05.txt, 01_max_06.txt, 01_max_07.txt, 01_max_08.txt, 01_max_09.txt, 01_max_10.txt, 01_max_11.txt, 01_max_12.txt, 01_max_13.txt, 01_max_14.txt, 01_max_15.txt, 01_max_16.txt, 01_max_17.txt, 01_max_18.txt, 01_max_19.txt, 01_max_20.txt, 01_max_21.txt, 01_max_22.txt, 02_random_23.txt, 02_random_24.txt, 02_random_25.txt, 02_random_26.txt, 02_random_27.txt, 02_random_28.txt, 02_random_29.txt, 02_random_30.txt, 02_random_31.txt, 02_random_32.txt, 02_random_33.txt, 02_random_34.txt, 02_random_35.txt, 02_random_36.txt, 02_random_37.txt, 02_random_38.txt, 03_handmade_39.txt, 03_handmade_40.txt, 03_handmade_41.txt, 03_handmade_42.txt, 03_handmade_43.txt, 03_handmade_44.txt, 03_handmade_45.txt, 03_handmade_46.txt
AfterContest 04_after_contest_47.txt
Case Name Status Exec Time Memory
00_sample_00.txt AC 8 ms 3544 KiB
00_sample_01.txt AC 2 ms 3540 KiB
00_sample_02.txt AC 2 ms 3412 KiB
01_max_03.txt AC 67 ms 9148 KiB
01_max_04.txt AC 65 ms 8888 KiB
01_max_05.txt AC 62 ms 9128 KiB
01_max_06.txt AC 64 ms 8888 KiB
01_max_07.txt AC 65 ms 9332 KiB
01_max_08.txt AC 80 ms 9492 KiB
01_max_09.txt AC 80 ms 9596 KiB
01_max_10.txt AC 82 ms 9596 KiB
01_max_11.txt AC 79 ms 9388 KiB
01_max_12.txt AC 78 ms 9488 KiB
01_max_13.txt AC 202 ms 17692 KiB
01_max_14.txt AC 188 ms 17608 KiB
01_max_15.txt AC 183 ms 17636 KiB
01_max_16.txt AC 184 ms 17680 KiB
01_max_17.txt AC 184 ms 17600 KiB
01_max_18.txt AC 233 ms 27120 KiB
01_max_19.txt AC 235 ms 26996 KiB
01_max_20.txt AC 229 ms 27088 KiB
01_max_21.txt AC 234 ms 27176 KiB
01_max_22.txt AC 231 ms 27000 KiB
02_random_23.txt AC 70 ms 9124 KiB
02_random_24.txt AC 67 ms 9088 KiB
02_random_25.txt AC 68 ms 9228 KiB
02_random_26.txt AC 83 ms 9160 KiB
02_random_27.txt AC 81 ms 9328 KiB
02_random_28.txt AC 83 ms 9272 KiB
02_random_29.txt AC 55 ms 7072 KiB
02_random_30.txt AC 141 ms 14736 KiB
02_random_31.txt AC 81 ms 9096 KiB
02_random_32.txt AC 105 ms 10384 KiB
02_random_33.txt AC 132 ms 12808 KiB
02_random_34.txt AC 5 ms 3624 KiB
02_random_35.txt AC 66 ms 8984 KiB
02_random_36.txt AC 2 ms 3624 KiB
02_random_37.txt AC 108 ms 10624 KiB
02_random_38.txt AC 52 ms 6480 KiB
03_handmade_39.txt AC 2 ms 3604 KiB
03_handmade_40.txt AC 64 ms 9008 KiB
03_handmade_41.txt AC 105 ms 14028 KiB
03_handmade_42.txt AC 127 ms 17688 KiB
03_handmade_43.txt AC 184 ms 27088 KiB
03_handmade_44.txt AC 5 ms 3616 KiB
03_handmade_45.txt AC 2 ms 3516 KiB
03_handmade_46.txt AC 62 ms 8948 KiB
04_after_contest_47.txt AC 147 ms 17708 KiB