Submission #50623295

---

Source Code Expand

#include <bits/stdc++.h>
#include <atcoder/modint>
const int MOD=998244353;
using mint = atcoder::static_modint<MOD>;
using namespace std;

typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)(n);i++)
#define per(i,a,n) for (ll i=n;i-->(ll)(a);)

#define SEG_ROOT(r) r,0,n+1
#define SEG_L seg[o].l
#define SEG_R seg[o].r
#define mid (l+r)/2
#define SEG_L_CHILD SEG_L,l,mid
#define SEG_R_CHILD SEG_R,mid,r

struct node{
  int l=-1;
  int r=-1;
  int v=0;
};
vector<node>seg;
int newnode(){
  int t=seg.size();
  seg.push_back(node{});
  return t;
}

ll read(){ll r;scanf("%lld",&r);return r;}
int n;
vector<int>p;

void pick(vector<int>pos){
  vector<int>isst(n,0);
  vector<pair<int,int> > st;
  for(auto i:pos) {
    st.push_back({p[i],i});
    isst[i]=true;
  }
  sort(begin(st),end(st),[](auto x,auto y){return y<x;});
  for(auto [v,stp]:st) {
    rep(i,stp,n){
      if(i!=stp and isst[i]) break; // 到下一个起点了
      printf("%d ",p[i]);
    }
  }
}

int query(int o,int l,int r,int ql,int qr){ // [l,r) [ql,qr)
  if(o==-1) return 0;
  if(ql <= l and r <= qr) return seg[o].v;
  int ret=0;
  if(ql < mid) ret += query(SEG_L_CHILD,ql,qr);
  if(qr > mid) ret += query(SEG_R_CHILD,ql,qr);
  // printf("query %d,[%d,%d) = %d\n",o,l,r,seg[o].v);
  return ret;
}
void up(int o){
  seg[o].v = 0;
  if(SEG_L!=-1) seg[o].v+=seg[SEG_L].v;
  if(SEG_R!=-1) seg[o].v+=seg[SEG_R].v;
}

int add(int o,int l,int r,int p){
  if(l+1==r){
    int v=newnode();
    seg[v].v=1;
    // printf("add leaf [p=%d] %d,[%d,%d) = %d\n",p,v,l,r,1);
    return v;
  }
  int v=newnode();
  if(o!=-1) { // clone
    seg[v].l=seg[o].l;
    seg[v].r=seg[o].r;
  }

  if(p< mid) seg[v].l=add(seg[v].l,l,mid,p);
  if(p>=mid) seg[v].r=add(seg[v].r,mid,r,p);
  up(v);
  // printf("add [p=%d] %d,[%d,%d) = %d\n",p,v,l,r,seg[v].v);
  return v;
}

int main(){
  n=read();
  int k=read();
  p.resize(n);
  rep(i,0,n) p[i]=read();
  if(k>=p[0]) { // 一定变 开头选1~k
    vector<int>pos;
    rep(i,0,n) if(p[i] <= k) pos.push_back(i);
    pick(pos);
    return 0;
  }

  vector<int> sz(n,0);
  sz[0]=1;
  vector<int> pre(n,0); // 最长严格下降上一个节点
  vector<int> idx; // val, 值严格下降, 个数=下标+1
  idx.push_back(0);
  rep(i,1,n) if(p[i] < p[0]){
    int l=0;
    int r=idx.size();
    while(r-l>1){ (p[idx[mid]] > p[i]?l:r) = mid; }
    pre[i] = idx[l];
    sz[i]=r+1;
    if(r < (int)idx.size()) {
      if(p[i] > p[idx[r]]) idx[r]=i;
    }else{
      idx.push_back(i);
    }
  }
  rep(i,0,n) if(sz[i] >= k) { // 可以完全不变
    pick({0});
    return 0;
  }
  // rep(i,0,n) printf("p=%d\tsz[%lld]=%d\n",p[i],i,sz[i]);
  vector<int> roots={newnode()}; // [n, n-1,....]
  pair<int,int> best={-1,-1};
  per(i,0,n) {
    if(p[i]<=p[0]){
      int s = sz[i];
      // 后面 选 k-s 个 < p[i]的
      int c=query(SEG_ROOT(roots.back()),1,p[i]);
      // printf("p[i]=%d search %d, less than=%d\n",p[i],k-s,c);
      if(c >= k-s) {// 能选出k-s个<p[i]
        int l=0;
        int r=roots.size()-1;
        while(r-l>1) (query(SEG_ROOT(roots[mid]),1,p[i]) >= k-s ?r:l)=mid;
        // {n-r,i}: n-r开始<p[i]}
        // printf("down to p[i]=%d, start from %d\n",p[i],p[n-r]);
        best=max(best,{n-r,i});
      }
      roots.push_back(add(SEG_ROOT(roots.back()),p[i]));
    }else{
      roots.push_back(roots.back());
    }
  }
  assert(best.first != -1);
  vector<int> pos;
  rep(i,best.first,n) if(p[i]<p[best.second]) pos.push_back(i);
  int i=best.second;
  while(true){
    pos.push_back(i);
    if(i==0)break;
    i=pre[i];
  }
  assert(pos.size()==k);
  pick(pos);
  return 0;
}
// ulimit -s 262144 #256mb stack

Submission Info

Compile Error

In file included from /usr/include/c++/12/cassert:44,
                 from /opt/ac-library/atcoder/internal_type_traits.hpp:4,
                 from /opt/ac-library/atcoder/internal_type_traits:1,
                 from /opt/ac-library/atcoder/modint.hpp:13,
                 from /opt/ac-library/atcoder/modint:1,
                 from Main.cpp:2:
Main.cpp: In function ‘int main()’:
Main.cpp:149:20: warning: comparison of integer expressions of different signedness: ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} and ‘int’ [-Wsign-compare]
  149 |   assert(pos.size()==k);
      |          ~~~~~~~~~~^~~
Main.cpp: In function ‘ll read()’:
Main.cpp:30:21: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   30 | ll read(){ll r;scanf("%lld",&r);return r;}
      |                ~~~~~^~~~~~~~~~~

Judge Result