Submission #12899490


Source Code Expand

Copy
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
//#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
//---------------------------------------------------------------------------------------------------
#define def make_pair(inf, inf)
template<class V, int NV> struct SegTree { //[l,r)
    V comp(V& l, V& r) { return min(l, r); };

    vector<V> val; SegTree() { val = vector<V>(NV * 2, def); }
    V get(int x, int y, int l = 0, int r = NV, int k = 1) {
        if (r <= x || y <= l)return def; if (x <= l && r <= y)return val[k];
        auto a = get(x, y, l, (l + r) / 2, k * 2); 
        auto b = get(x, y, (l + r) / 2, r, k * 2 + 1);
        return comp(a, b);
    }
    void update(int i, V v) {
        i += NV; val[i] = v;
        while (i>1) i >>= 1, val[i] = comp(val[i * 2], val[i * 2 + 1]);
    }
    void add(int i, V v) { update(i, val[i + NV] + v); }
    V operator[](int x) { return get(x, x + 1); }
};
/*---------------------------------------------------------------------------------------------------
            ∧_∧
      ∧_∧  (´<_` )  Welcome to My Coding Space!
     ( ´_ゝ`) /  ⌒i     @hamayanhamayan0
    /   \     | |
    /   / ̄ ̄ ̄ ̄/  |
  __(__ニつ/     _/ .| .|____
     \/____/ (u ⊃
---------------------------------------------------------------------------------------------------*/














int N, K, D, A[201010];
SegTree<pair<int, int>, 1 << 18> st;
int ans[201010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> K >> D;
    rep(i, 0, N) cin >> A[i];
    rep(i, 0, N) st.update(i, make_pair(A[i], i));

    int idx = 0;
    rep(k, 0, K) {
        int rest = K - k;

        // [L, R]
        int L = idx;
        int R = N - 1 - ((rest - 1) * D);

        if (R < L) {
            cout << -1 << endl;
            return;
        }
        
        auto p = st.get(L, R + 1);
        ans[k] = p.first;
        idx = p.second + D;
    }

    rep(i, 0, K) {
        if(i) printf(" ");
        printf("%d", ans[i]);
    }
    printf("\n");
}





Submission Info

Submission Time
Task L - Lexicographically Minimum
User hamayanhamayan
Language C++ (GCC 9.2.1)
Score 6
Code Size 2791 Byte
Status
Exec Time 77 ms
Memory 8756 KB

Compile Error

./Main.cpp: In member function ‘V SegTree<V, NV>::get(int, int, int, int, int)’:
./Main.cpp:18:9: warning: this ‘if’ clause does not guard... [-Wmisleading-indentation]
   18 |         if (r <= x || y <= l)return def; if (x <= l && r <= y)return val[k];
      |         ^~
./Main.cpp:18:42: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the ‘if’
   18 |         if (r <= x || y <= l)return def; if (x <= l && r <= y)return val[k];
      |                                          ^~

Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 s1.txt, s2.txt, s3.txt, s4.txt
All 6 / 6 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, s1.txt, s2.txt, s3.txt, s4.txt
Case Name Status Exec Time Memory
01.txt 40 ms 8168 KB
02.txt 30 ms 7904 KB
03.txt 18 ms 7704 KB
04.txt 17 ms 7260 KB
05.txt 23 ms 7640 KB
06.txt 39 ms 8076 KB
07.txt 27 ms 7796 KB
08.txt 19 ms 7656 KB
09.txt 6 ms 7164 KB
10.txt 25 ms 7900 KB
11.txt 32 ms 8168 KB
12.txt 26 ms 7528 KB
13.txt 31 ms 8196 KB
14.txt 32 ms 8064 KB
15.txt 7 ms 7132 KB
16.txt 5 ms 7220 KB
17.txt 9 ms 7256 KB
18.txt 12 ms 7216 KB
19.txt 28 ms 7668 KB
20.txt 57 ms 8440 KB
21.txt 49 ms 8328 KB
22.txt 61 ms 8692 KB
23.txt 33 ms 8168 KB
24.txt 32 ms 8084 KB
25.txt 33 ms 7792 KB
26.txt 23 ms 7488 KB
27.txt 59 ms 8756 KB
28.txt 32 ms 8220 KB
29.txt 52 ms 8320 KB
30.txt 32 ms 8064 KB
31.txt 68 ms 8612 KB
32.txt 71 ms 8604 KB
33.txt 66 ms 8640 KB
34.txt 56 ms 8444 KB
35.txt 35 ms 8232 KB
36.txt 77 ms 8660 KB
37.txt 30 ms 8200 KB
s1.txt 7 ms 7284 KB
s2.txt 6 ms 7220 KB
s3.txt 7 ms 7220 KB
s4.txt 5 ms 7148 KB