Submission #53104244

Source Code Expand

// #pragma GCC optimize("Ofast,unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define inf (ll)1e18
#define pll pair<ll, ll>
#define vi vector<int>
#define vl vector<ll>
#define fi first
#define se second
#define lll __int128
const int N = 1e6 + 5;
ll n, k, p[N];
void solve() {
    cin >> n >> k;
    for (ll i = 1; i <= n; i++)
        cin >> p[i];
    set<ll> s;
    map<ll, ll> mp;
    for (ll i = 1; i <= n; i++)
        mp[p[i]] = i;
    for (ll i = 1; i <= k; i++)
        s.insert(mp[i]);
    ll ans = *(--s.end()) - *s.begin();
    for (ll i = k + 1; i <= n; i++) {
        s.erase(mp[i - k]);
        s.insert(mp[i]);
        ans = min(ans, *(--s.end()) - *s.begin());
    }
    cout << ans << endl;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}

Submission Info

Submission Time
Task D - Permutation Subsequence
User TopCloser
Language C++ 20 (gcc 12.2)
Score 425
Code Size 893 Byte
Status AC
Exec Time 272 ms
Memory 26848 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 425 / 425
Status
AC × 3
AC × 28
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_random_00.txt, 01_random_01.txt, 01_random_02.txt, 01_random_03.txt, 01_random_04.txt, 01_random_05.txt, 01_random_06.txt, 01_random_07.txt, 01_random_08.txt, 01_random_09.txt, 01_random_10.txt, 01_random_11.txt, 01_random_12.txt, 01_random_13.txt, 01_random_14.txt, 01_random_15.txt, 01_random_16.txt, 01_random_17.txt, 02_random2_00.txt, 02_random2_01.txt, 02_random2_02.txt, 02_random2_03.txt, 02_random2_04.txt, 03_handmade_00.txt, 03_handmade_01.txt
Case Name Status Exec Time Memory
00_sample_00.txt AC 1 ms 3476 KiB
00_sample_01.txt AC 1 ms 3624 KiB
00_sample_02.txt AC 1 ms 3436 KiB
01_random_00.txt AC 121 ms 17624 KiB
01_random_01.txt AC 229 ms 21620 KiB
01_random_02.txt AC 62 ms 9812 KiB
01_random_03.txt AC 236 ms 23012 KiB
01_random_04.txt AC 225 ms 20560 KiB
01_random_05.txt AC 263 ms 22148 KiB
01_random_06.txt AC 185 ms 16476 KiB
01_random_07.txt AC 246 ms 25332 KiB
01_random_08.txt AC 215 ms 24312 KiB
01_random_09.txt AC 266 ms 20648 KiB
01_random_10.txt AC 40 ms 8928 KiB
01_random_11.txt AC 272 ms 24840 KiB
01_random_12.txt AC 20 ms 5968 KiB
01_random_13.txt AC 264 ms 22744 KiB
01_random_14.txt AC 67 ms 12284 KiB
01_random_15.txt AC 162 ms 17472 KiB
01_random_16.txt AC 247 ms 26848 KiB
01_random_17.txt AC 1 ms 3428 KiB
02_random2_00.txt AC 113 ms 26396 KiB
02_random2_01.txt AC 107 ms 20364 KiB
02_random2_02.txt AC 117 ms 18084 KiB
02_random2_03.txt AC 128 ms 19116 KiB
02_random2_04.txt AC 127 ms 24968 KiB
03_handmade_00.txt AC 124 ms 20756 KiB
03_handmade_01.txt AC 118 ms 20768 KiB