Submission #1135951

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135951		altern23	Stone Arranging 2 (JOI23_ho_t1)	C++20	35 / 100	68 ms	11776 KiB

Main

#include <bits/stdc++.h>
using namespace std;
 
#pragma GCC optimize ("O2")
#pragma GCC optimize ("unroll-loops")
 
#define ll long long
#define pii pair<ll,ll>
#define fi first
#define sec second
#define ld long double

template <typename T>
ostream& operator << (ostream& os, vector<T>tmp){
    os << "[";
    for(auto x : tmp) os << " " << x;
    os << " ]";
 
    return os;
}
 
template <typename T>
ostream& operator << (ostream& os, set<T>tmp){
    os << "[";
    for(auto x : tmp) os << " " << x;
    os << " ]";
 
    return os;
}
 
template <typename T>
ostream& operator << (ostream& os, multiset<T>tmp){
    os << "[";
    for(auto x : tmp) os << " " << x;
    os << " ]";
 
    return os;
}

ostream& operator << (ostream& os, pii x){
    os << "[";
    os << " " << x.fi << " " << x.sec;
    os << " ]";
 
    return os;
}

ostream& operator << (ostream& os, pair<pii, ll> x){
    os << "[";
    os << " " << x.fi << " " << x.sec;
    os << " ]";
 
    return os;
}

ostream& operator << (ostream& os, pair<ll, pii> x){
    os << "[";
    os << " " << x.fi << " " << x.sec;
    os << " ]";
 
    return os;
}

const ll MOD = 1e9 + 7;
const ll N = 2e3 + 5;
const ll INF = 2e18;

// modulo operations
void add(ll &a, ll b) { a = (a + b) % MOD; }
void sub(ll &a, ll b) { a -= b; while(a < 0) a += MOD; a %= MOD; }
void mul(ll &a, ll b) { a = (a * b) % MOD; }

ll expo(ll a, ll b) {
    ll ans = 1;
    while(b > 0){
        if(b & 1) mul(ans, a);
        mul(a, a);
        b /= 2;
    }

    return ans;
}

int32_t main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int tc = 1;
    // cin >> tc;
    for(;tc--;){
        ll n; cin >> n;
        vector<ll> a(n + 5);
        vector<ll> comp;
        for(int i = 1; i <= n; i++){
            cin >> a[i];
            comp.push_back(a[i]);
        }

        sort(comp.begin(), comp.end());
        comp.erase(unique(comp.begin(), comp.end()), comp.end());

        map<ll, ll> id, rev;
        ll cur = 0;
        for(auto &x : comp){
            id[x] = ++cur;
            rev[cur] = x;
        }

        for(int i = 1; i <= n; i++) a[i] = id[a[i]];

        vector<ll> pos[cur + 5];
        multiset<pair<pii, ll>> ms;

        auto add = [&](ll L, ll R, ll color){
            pair<pii, ll> now = {{L, R}, -INF};
            auto x = ms.lower_bound(now);
            if(x != ms.end()){
                vector<pair<pii, ll>> del;
                for(auto y = x; y != ms.end(); ++y){
                    ll curL = (*y).fi.fi, curR = (*y).fi.sec;
                    if(curL >= L && curR <= R){
                        del.push_back((*y));
                    }
                    else break;
                }

                for(auto &y : del) ms.erase(y);
            }

            ms.insert({{L, R}, color});
        };

        for(int i = 1; i <= n; i++){
            for(;!pos[a[i]].empty();){
                bool ok = 1;
                if(!ms.empty()){
                    pair<pii, ll> now = {{pos[a[i]].back(), INF}, INF};
                    auto x = ms.upper_bound(now);
                    if(x != ms.begin()){
                        --x;
                        ll L = (*x).fi.fi, R = (*x).fi.sec, color = (*x).sec;

                        if(color == a[i]){
                            ms.erase(*x);
                            L = min(L, pos[a[i]].back()), R = max(R, (ll)i);
                            add(L, R, color);
                            goto next;
                        }

                        if(L <= pos[a[i]].back() && pos[a[i]].back() <= R){
                            ok = 0;
                            pos[a[i]].pop_back();
                        }
                    }
                }

                if(ok) break;
            }

            if(pos[a[i]].size()){
                add(pos[a[i]].back(), i, rev[a[i]]);
            }

            next:

            pos[a[i]].push_back(i);
        }

        vector<ll> ans(n + 5);
        for(auto &x : ms){
            ll L = x.fi.fi, R = x.fi.sec, color = x.sec;
            for(int i = L; i <= R; i++) ans[i] = color;
        }

        for(int i = 1; i <= n; i++){
            if(!ans[i]) cout << rev[a[i]] << "\n";
            else cout << ans[i] << "\n";
        }
    }   
}

/*


*/

• Subtask 1: 0 / 25
• Subtask 2: 35 / 35
• Subtask 3: 0 / 40