Submission #1128457

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128457		ByeWorld	Stone Arranging 2 (JOI23_ho_t1)	C++20	100 / 100	305 ms	29320 KiB

Main

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define int long long
#define ll long long
#define pb push_back
#define fi first
#define se second
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
#define ld long double
using namespace std;
typedef pair<int,int> pii;
typedef pair<char,char> pcc;
typedef pair<int,pii> ipii;
typedef pair<pii,pii> ipiii;
const int MAXN = 3e5+10;
const int MAXA = 1e6;
const int INF = 1e18+10;
const int MOD = 1e9+7;
const int LOG = 33;
const ld EPS = 1e-12;
void chmn(int &a, int b){ a = min(a, b); }
int sum(int a, int b){ return (a+b)%MOD; }
int mul(int a, int b){ return (1ll*a*b)%MOD; }
void chmul(int &a, int b){ a = (1ll*a*b)%MOD; }
void chsum(int &a, int b){ a = (a+b)%MOD; }
int expo(int a, int b){
    a %= MOD;
    if(b==0) return 1;
    int te = expo(a,b/2); te=mul(te,te);
    return (b%2 ? mul(te, a) : te);
}

int n, las[MAXN], a[MAXN], ans[MAXN];
set <pii> s;

struct seg {
    int st[4*MAXN], laz[4*MAXN];
    void bnc(int id, int l, int r){
        if(laz[id] == 0) return;
        laz[lf] = laz[id]; st[lf] = laz[id];
        laz[rg] = laz[id]; st[rg] = laz[id];
        laz[id] = 0;
    }
    int upd(int id,int l,int r, int x, int y, int p){
        if(x<=l && r<=y){
            laz[id] = p;
            return st[id] = p;
        }
        if(r<x || y<l) return st[id];
        bnc(id,l,r);
        return st[id] = min(upd(lf,l,md,x,y,p), upd(rg,md+1,r,x,y,p));
    }
    int que(int id,int l,int r, int x, int y){
        if(x<=l && r<=y) return st[id];
        if(r<x || y<l) return INF;
        bnc(id,l,r);
        return min(que(lf,l,md,x,y), que(rg,md+1,r,x,y));
    }
    void OUT(int id,int l, int r){
        if(l==r){ ans[l] = st[id]; return; }
        bnc(id,l,r);
        OUT(lf,l,md); OUT(rg,md+1,r);
    }
} A;
signed main(){
    // ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n;
    vector <int> cc; cc.pb(-1);
    for(int i=1; i<=n; i++){
        cin >> a[i]; cc.pb(a[i]);
    }
    sort(cc.begin(), cc.end());
    cc.resize(unique(cc.begin(), cc.end()) - cc.begin());
    for(int i=1; i<=n; i++) las[i] = -1;

    for(int i=1; i<=n; i++){
        a[i] = lower_bound(cc.begin(), cc.end(), a[i]) - cc.begin();
        if(las[a[i]] == -1){
            A.upd(1,1,n,i,i,a[i]);
            las[a[i]] = i; s.insert({i, a[i]});
        } else {
            int le = las[a[i]];
            A.upd(1,1,n,las[a[i]],i, a[i]);

            while(s.lower_bound(pii(le, -1)) != s.end()){
                auto it = s.lower_bound(pii(le, -1)); 
                int val = (*it).se, idx = (*it).fi;
                s.erase(it);
                if(idx==1 || A.que(1,1,n,idx-1,idx-1) != val)
                    las[val] = -1;
                else las[val] = idx-1;
            }

            las[a[i]] = i; s.insert({i, a[i]});
        }
            // cout <<i << " i\n";
            // for(auto [x,y] : s) cout << x << ' ' << y << " xy\n";
    }  
    A.OUT(1,1,n);

    for(int i=1; i<=n; i++){
        cout << cc[ans[i]] << '\n';
    }
}

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