Submission #862055

#	Time	Username	Problem	Language	Result	Execution time	Memory
862055		sleepntsheep	Stone Arranging 2 (JOI23_ho_t1)	C++17	100 / 100	108 ms	23636 KiB

Main

#include <cstdio>
#include <cstring>
#include <cassert>
#include <string>
#include <deque>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
#include <iostream>
#include <utility>
using namespace std;
using ll = long long;
using ld = long double;
#define ShinLena cin.tie(nullptr)->sync_with_stdio(false)

#define N 200005
#define ALL(x) x.begin(), x.end()

int n, a[N], b[N], c[N], C, t[N<<2], lz[N<<2];
vector<int> at[N];

void build(int v, int l, int r)
{
    if (l == r) t[v] = a[l];
    else build(2*v+1, l, (l+r)/2), build(2*v+2, (l+r)/2+1, r);
}

void push(int v, int l, int r)
{
    if (lz[v])
    {
        if (l != r) lz[2*v+1] = lz[2*v+2] = lz[v];
        t[v] = lz[v];
        lz[v] = 0;
    }
}

void upd(int v, int l, int r, int x, int y, int k)
{
    push(v, l, r);
    if (r < x||y<l)return;
    if(x<=l&&r<=y){lz[v]=k;push(v,l,r);return;}
    upd(2*v+1, l,(l+r)/2,x,y,k),upd(2*v+2,(l+r)/2+1,r,x,y,k);
}

int qry(int v,int l,int r,int p)
{
    push(v,l,r);
    if (l==r)return t[v];
    if(p<=(l+r)/2)return qry(2*v+1,l,(l+r)/2,p);
    return qry(2*v+2, (l+r)/2+1, r, p);
}

void ans(int v, int l, int r)
{
    push(v,l,r);
    if (l == r) a[l]= t[v];
    else ans(2*v+1,l,(l+r)/2), ans(2*v+2, (l+r)/2+1,r);
}

int main()
{
    ShinLena;
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i], b[C++] = a[i];
    sort(b, b+C); C = unique(b, b+C) - b;
    for (int i = 1; i <= n; ++i) { int x = lower_bound(b, b+C, a[i]) - b + 1, old = a[i]; c[a[i] = x] = old; }

    build(0,1,n);

    for (int i = 1; i <= n; ++i)
    {
        while(at[a[i]].size() && qry(0,1,n,at[a[i]].back()) != a[i]) at[a[i]].pop_back();
        if (at[a[i]].size()) upd(0, 1, n,at[a[i]].back()+1,i-1, a[i]);
        at[a[i]].push_back(i);
    }

    ans(0,1,n);
    for(int i=1;i<=n;++i)cout<<c[a[i]]<<'\n';

    return 0;
}

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