Submission #50624050

---

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{-1,-1,0});
  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);
  return ret;
}

int add(int o,int l,int r,int p){
  assert(1<=p and p<=n);
  if(l+1==r){
    assert(o==-1);
    int v=newnode();
    seg[v].v=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);

  seg[v].v = 0;
  if(seg[v].l!=-1) seg[v].v+=seg[seg[v].l].v;
  if(seg[v].r!=-1) seg[v].v+=seg[seg[v].r].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;
  }
  vector<int> roots={-1}; // [n, n-1,....]
  array<int,3> best={-1,-1,-1}; // 后缀选择起始下标, 选点个数, 前缀单调下降最后一个起始值下标（比较值下标)
  per(i,0,n) {
    if(p[i]<=p[0]){
      int s = sz[i];
      assert(s<k);
      // 后面 选 k-s 个 < p[i]的
      int c=query(SEG_ROOT(roots.back()),1,p[i]);
      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]}
        if(n-r > best[0]){
          best = {n-r,k-s,(int)i};
        }else if(n-r == best[0]){ // 起始相等 待选点越少越好
          if(k-s < best[1]) {
            best = {n-r,k-s,(int)i};
          }
        }
      }
      roots.push_back(add(SEG_ROOT(roots.back()),p[i]));
    }else{
      roots.push_back(roots.back());
    }
  }
  assert(best[0] != -1);
  auto [si,_,pi] = best;
  assert(pi<si);
  vector<int> pos;
  rep(i,si,n) if(p[i]<p[pi]) pos.push_back(i);
  int i=pi;
  while(true){
    pos.push_back(i);
    if(i==0) break;
    i=pre[i];
  }
  assert((int)pos.size()==k);
  pick(pos);
  return 0;
}

Submission Info

Compile Error

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