Submission #7641468


Source Code Expand

Copy
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define int long long
using namespace std;
typedef pair<int, int> P;
const int mod = 1000000007;
const int INF = 1e18;

template< typename T, typename E >
struct SegmentTree{
    using F = function< T(T, T) >;
    using G = function< T(T, E) >;
    int sz;
    vector<T> dat;
    F f;
    G g;
    T t1;
    SegmentTree(int n, F f, G g, T t1) : f(f), g(g), t1(t1) {
        sz = 1;
        while(sz < n) sz *= 2;
        dat.clear();
        dat.resize(2 * sz - 1, t1);
    }
    void set(int k, T x) { dat[k + sz - 1] = x; }
    void build() {
        for(int k = sz - 2; k >= 0; k--) {
            dat[k] = f(dat[2 * k + 1], dat[2 * k + 2]);
        }
    }
    void update(int k, E x) {
        k += sz - 1;
        dat[k] = g(dat[k], x);
        while(k > 0) {
            k = (k - 1) / 2;
            dat[k] = f(dat[2 * k + 1], dat[2 * k + 2]);
        }
    }
    T query(int a, int b, int k, int l, int r) {
        if(r <= a || b <= l) return t1;
        if(a <= l && r <= b) return dat[k];
        T vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
        T vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
        return f(vl, vr);
    }
    T query(int a, int b){ return query(a, b, 0, 0, sz); }
    T operator[](int k) { return dat[k + sz - 1]; }
};

vector<vector<int> > split_vector(vector<int> &a, int pivot){
    vector<vector<int> > res;
    a.push_back(pivot);
    for(int i = 0; i < a.size(); i++){
        vector<int> tmp;
        while(i < a.size() && a[i] != pivot){
            tmp.push_back(a[i++]);
        }
        if(tmp.size() != 0) res.push_back(tmp);
    }
    a.pop_back();
    return res;
}

signed main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n, k;
    cin >> n >> k;
    vector<int> p(n);
    rep(i, 0, n) cin >> p[i];
    SegmentTree<int, int> rmq(n,
        [](int a, int b){ return min(a, b); },
        [](int a, int b){ return b; },
        INT_MAX);
    SegmentTree<int, int> RMQ(n,
        [](int a, int b){ return max(a, b); },
        [](int a, int b){ return b; },
        -1);
    rep(i, 0, n){
        rmq.update(i, p[i]);
        RMQ.update(i, p[i]);
    }
    int ans = 1;
    for(int i = 0; i < n - k; i++){
        // [i, i + k) と [i + 1, i + k + 1) が同じかどうか
        // p[i] = rmq[i, i + k) and p[i + k] = RMQ[i + 1, i + k + 1)
        if(p[i] == rmq.query(i, i + k) && p[i + k] == RMQ.query(i + 1, i + k + 1)) continue;
        ans++;
    }
    // ソート済みかどうか
    vector<int> a(n), b(n - k + 1);
    rep(i, 0, n - 1){
        if(p[i] > p[i + 1]) a[i] = 1;
    }
    int tmp = 0;
    rep(i, 0, k - 2) tmp += a[i];
    for(int i = 0; i < n - k + 1; i++){
        tmp += a[i + k - 2];
        // cout << i << ' ' << tmp << endl;
        if(tmp == 0) b[i] = 1;
        tmp -= a[i];
    }
    vector<vector<int> > c = split_vector(b, 0);
    if(c.size()) ans -= c.size() - 1;
    cout << ans << endl;
}

Submission Info

Submission Time
Task B - Sorting a Segment
User treeone
Language C++14 (GCC 5.4.1)
Score 700
Code Size 3076 Byte
Status AC
Exec Time 144 ms
Memory 18276 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 700 / 700
Status
AC × 3
AC × 32
Set Name Test Cases
Sample sample-01.txt, sample-02.txt, sample-03.txt
All 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 01-23.txt, 01-24.txt, 01-25.txt, 01-26.txt, 01-27.txt, 01-28.txt, 01-29.txt, sample-01.txt, sample-02.txt, sample-03.txt
Case Name Status Exec Time Memory
01-01.txt AC 1 ms 256 KB
01-02.txt AC 1 ms 256 KB
01-03.txt AC 76 ms 13312 KB
01-04.txt AC 101 ms 12928 KB
01-05.txt AC 46 ms 6784 KB
01-06.txt AC 84 ms 13080 KB
01-07.txt AC 120 ms 18276 KB
01-08.txt AC 87 ms 16128 KB
01-09.txt AC 115 ms 14720 KB
01-10.txt AC 111 ms 15360 KB
01-11.txt AC 90 ms 15872 KB
01-12.txt AC 139 ms 14720 KB
01-13.txt AC 126 ms 14720 KB
01-14.txt AC 94 ms 14592 KB
01-15.txt AC 144 ms 14592 KB
01-16.txt AC 127 ms 15104 KB
01-17.txt AC 71 ms 12928 KB
01-18.txt AC 103 ms 13184 KB
01-19.txt AC 100 ms 13312 KB
01-20.txt AC 118 ms 14604 KB
01-21.txt AC 94 ms 13152 KB
01-22.txt AC 63 ms 12288 KB
01-23.txt AC 85 ms 12672 KB
01-24.txt AC 82 ms 12672 KB
01-25.txt AC 50 ms 11648 KB
01-26.txt AC 56 ms 11776 KB
01-27.txt AC 50 ms 11648 KB
01-28.txt AC 48 ms 11648 KB
01-29.txt AC 48 ms 11648 KB
sample-01.txt AC 1 ms 256 KB
sample-02.txt AC 1 ms 256 KB
sample-03.txt AC 1 ms 256 KB