oj.uz

Submission #635828

# Submission time Handle Problem Language Result Execution time Memory
635828 2022-08-27T06:23:20 Z MohammadAghil Watermelon (INOI20_watermelon) C++17
31 / 100
 102 ms 13508 KB 
#include <bits/stdc++.h>
//#pragma GCC optimize ("Ofast,unroll-loops")
//#pragma GCC target ("avx2")
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pp;
 
#define rep(i,l,r) for(int i = (l); i < (r); i++)
#define per(i,r,l) for(int i = (r); i >= (l); i--)
#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()
#define pb push_back
#define ff first
#define ss second
 
void dbg(){
    cerr << endl;
}
template<typename Head, typename... Tail> void dbg(Head h, Tail... t){
    cerr << " " << h << ",";
    dbg(t...);
}
#define er(...) cerr << __LINE__ << " <" << #__VA_ARGS__ << ">:", dbg(__VA_ARGS__)
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
void IOS(){
    cin.tie(0) -> sync_with_stdio(0);
    // #ifndef ONLINE_JUDGE
    //     freopen("inp.txt", "r", stdin);
    //     freopen("out.txt", "w", stdout);
    // #endif
}

const ll mod = 1e9 + 7, maxn = 1e5 + 5, lg = 20, inf = ll(1e9) + 5;

vector<int> adj[maxn];
 
int fen[maxn];
void upd(int i, int k){
    for(i++; i < maxn; i += i&-i) fen[i] = max(fen[i], k);
}
int get(int i){
    int res = 0;
    for(i++; i; i -= i&-i) res = max(res, fen[i]);
    return res;
}
vector<int> val(vector<int> p){
    int n = sz(p);
    vector<int> res(n);
    vector<int> stk;
    per(i,n-1,0){
        while(sz(stk) && p[stk.back()] < p[i]) stk.pop_back();
        if(sz(stk)){
            res[i] = get(stk.back()-1) + 1;
        }else res[i] = inf;
        upd(i, res[i]);
        stk.pb(i);
    }
    int tmp = n;
    rep(i,0,n) res[i] += res[i] == inf? tmp--: 0;
    return res;
}

int main(){ IOS();
    int n, k; cin >> n >> k;
    vector<int> a(n);
    int tmp = n;
    rep(i,0,n) {
        cin >> a[i];
        if(a[i] == -1){
            a[i] = inf + tmp, tmp--;
        }
    }

    vector<int> stk, cnt(n);
    rep(i,0,n){
        while(sz(stk) && a[stk.back()] < a[i]) stk.pop_back();
        if(sz(stk)){
            if(a[i] - a[stk.back()]){
                adj[i].pb(stk.back());
                cnt[stk.back()]++;
            } 
        }
        stk.pb(i);
    }
    stk.clear();
    per(i,n-1,0){
        while(sz(stk) && a[stk.back()] < a[i]) stk.pop_back();
        if(sz(stk)){
            adj[i].pb(stk.back());
            cnt[stk.back()]++;
        }
        stk.pb(i);
    }
    
    set<pp> s;
    rep(i,0,n) s.insert({cnt[i], i});
    vector<int> ans(n);
    int ptr = 0;
    while(sz(s) && begin(s)->ff == 0){
        auto[_, r] = *begin(s);
        s.erase(begin(s));
        ans[r] = ptr++;
        for(int c: adj[r]){
            s.erase(pp(cnt[c], c));
            s.insert(pp(--cnt[c], c));
        }
    }
    
    if(sz(s) || val(ans) != a){
        cout << -1 << '\n';
    } else{
        for(int c: ans) cout << ++c << ' ';
        cout << '\n';
    }
    return 0;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2668 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 1 ms 2644 KB Output is correct
7 Correct 2 ms 2676 KB Output is correct
8 Correct 2 ms 2680 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Incorrect 2 ms 2644 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2668 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 1 ms 2644 KB Output is correct
7 Correct 2 ms 2676 KB Output is correct
8 Correct 2 ms 2680 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Incorrect 2 ms 2644 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 7628 KB Output is correct
2 Correct 43 ms 7316 KB Output is correct
3 Correct 46 ms 7792 KB Output is correct
4 Correct 43 ms 7568 KB Output is correct
5 Correct 47 ms 7664 KB Output is correct
6 Correct 42 ms 7660 KB Output is correct
7 Correct 53 ms 7748 KB Output is correct
8 Correct 44 ms 7672 KB Output is correct
9 Correct 43 ms 7676 KB Output is correct
10 Correct 45 ms 7756 KB Output is correct
11 Correct 89 ms 12780 KB Output is correct
12 Correct 102 ms 12788 KB Output is correct
13 Correct 90 ms 12832 KB Output is correct
14 Correct 86 ms 12848 KB Output is correct
15 Correct 92 ms 12516 KB Output is correct
16 Correct 92 ms 12616 KB Output is correct
17 Correct 93 ms 12528 KB Output is correct
18 Correct 96 ms 12616 KB Output is correct
19 Correct 94 ms 12620 KB Output is correct
20 Correct 93 ms 12616 KB Output is correct
21 Correct 91 ms 12520 KB Output is correct
22 Correct 96 ms 12624 KB Output is correct
23 Correct 95 ms 12600 KB Output is correct
24 Correct 94 ms 13368 KB Output is correct
25 Correct 80 ms 13208 KB Output is correct
26 Correct 76 ms 13244 KB Output is correct
27 Correct 72 ms 13152 KB Output is correct
28 Correct 75 ms 13212 KB Output is correct
29 Correct 72 ms 13260 KB Output is correct
30 Correct 21 ms 5736 KB Output is correct
31 Correct 37 ms 7804 KB Output is correct
32 Correct 63 ms 11880 KB Output is correct
33 Correct 72 ms 13004 KB Output is correct
34 Correct 8 ms 3632 KB Output is correct
35 Correct 14 ms 4756 KB Output is correct
36 Correct 41 ms 7760 KB Output is correct
37 Correct 72 ms 12948 KB Output is correct
38 Correct 81 ms 12860 KB Output is correct
39 Correct 75 ms 12976 KB Output is correct
40 Correct 85 ms 13084 KB Output is correct
41 Correct 80 ms 13508 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 7628 KB Output is correct
2 Correct 43 ms 7316 KB Output is correct
3 Correct 46 ms 7792 KB Output is correct
4 Correct 43 ms 7568 KB Output is correct
5 Correct 47 ms 7664 KB Output is correct
6 Correct 42 ms 7660 KB Output is correct
7 Correct 53 ms 7748 KB Output is correct
8 Correct 44 ms 7672 KB Output is correct
9 Correct 43 ms 7676 KB Output is correct
10 Correct 45 ms 7756 KB Output is correct
11 Correct 89 ms 12780 KB Output is correct
12 Correct 102 ms 12788 KB Output is correct
13 Correct 90 ms 12832 KB Output is correct
14 Correct 86 ms 12848 KB Output is correct
15 Correct 92 ms 12516 KB Output is correct
16 Correct 92 ms 12616 KB Output is correct
17 Correct 93 ms 12528 KB Output is correct
18 Correct 96 ms 12616 KB Output is correct
19 Correct 94 ms 12620 KB Output is correct
20 Correct 93 ms 12616 KB Output is correct
21 Correct 91 ms 12520 KB Output is correct
22 Correct 96 ms 12624 KB Output is correct
23 Correct 95 ms 12600 KB Output is correct
24 Correct 94 ms 13368 KB Output is correct
25 Correct 80 ms 13208 KB Output is correct
26 Correct 76 ms 13244 KB Output is correct
27 Correct 72 ms 13152 KB Output is correct
28 Correct 75 ms 13212 KB Output is correct
29 Correct 72 ms 13260 KB Output is correct
30 Correct 21 ms 5736 KB Output is correct
31 Correct 37 ms 7804 KB Output is correct
32 Correct 63 ms 11880 KB Output is correct
33 Correct 72 ms 13004 KB Output is correct
34 Correct 8 ms 3632 KB Output is correct
35 Correct 14 ms 4756 KB Output is correct
36 Correct 41 ms 7760 KB Output is correct
37 Correct 72 ms 12948 KB Output is correct
38 Correct 81 ms 12860 KB Output is correct
39 Correct 75 ms 12976 KB Output is correct
40 Correct 85 ms 13084 KB Output is correct
41 Correct 80 ms 13508 KB Output is correct
42 Incorrect 42 ms 7692 KB Output isn't correct
43 Halted 0 ms 0 KB -

Subtask #5
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2668 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 1 ms 2644 KB Output is correct
7 Correct 2 ms 2676 KB Output is correct
8 Correct 2 ms 2680 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Incorrect 2 ms 2644 KB Output isn't correct
13 Halted 0 ms 0 KB -