Submission #635828

#	Time	Username	Problem	Language	Result	Execution time	Memory
635828		MohammadAghil	Watermelon (INOI20_watermelon)	C++17	31 / 100	102 ms	13508 KiB

Main

#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
• Subtask 2: 0 / 25
• Subtask 3: 31 / 31
• Subtask 4: 0 / 18
• Subtask 5: 0 / 19