Submission #1293618

#	Time	Username	Problem	Language	Result	Execution time	Memory
1293618		haha	Stone Arranging 2 (JOI23_ho_t1)	C++20	100 / 100	101 ms	10156 KiB

Main

#include <bits/stdc++.h>
#define f first
#define s second
#define ll long long
using namespace std;
const int maxn=2e5+5;

int n;
int a[maxn];
int pos[maxn],len[maxn];
int tree[4*maxn],lazy[4*maxn];
vector<int> nen;
vector<int> trace;

void down(int id)
{
    int d=lazy[id];
    tree[id*2]+=d;
    tree[id*2+1]+=d;
    lazy[id*2]+=d;
    lazy[id*2+1]+=d;
    lazy[id]=0;
}

void update(int id,int l,int r,int u,int v,int d)
{
    if(r<u||v<l) return;
    if(u<=l&&r<=v){
        tree[id]+=d;
        lazy[id]+=d;
        return;
    }
    int mid=(l+r)/2;
    down(id);
    update(id*2,l,mid,u,v,d);
    update(id*2+1,mid+1,r,u,v,d);
    tree[id]=max(tree[id*2],tree[id*2+1]);
}

int get(int id,int l,int r,int u,int v)
{
    if(r<u||v<l) return 0;
    if(u<=l&&r<=v) return tree[id];
    int mid=(l+r)/2;
    down(id);
    return max(get(id*2,l,mid,u,v),get(id*2+1,mid+1,r,u,v));

}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        nen.push_back(a[i]);
    }
    sort(nen.begin(),nen.end());
    nen.erase(unique(nen.begin(),nen.end()),nen.end());
    for(int i=1;i<=n;i++) a[i]=lower_bound(nen.begin(),nen.end(),a[i])-nen.begin()+1;
    for(int i=1;i<=n;i++){
        if(pos[a[i]]==0){
            len[i]=1;
        }
        else{
            int pre=pos[a[i]];
            if(get(1,1,n,pre,pre)==0){
                len[i]=i-pre;
                update(1,1,n,pre,i-1,1);
            }
            else len[i]=1;
        }
        pos[a[i]]=i;
    }

    int i=n;
    while(i>=1){
        int val=a[i];
        for(int j=1;j<=len[i];j++){
            trace.push_back(nen[val-1]);
        }
        i-=len[i];
    }
    reverse(trace.begin(),trace.end());
    for(int i=0;i<trace.size();i++) cout<<trace[i]<<'\n';

}

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