Submission #67656630

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=(a);i<(n);i++)
#define per(i,a,n) for (int i=(n)-1;i>=(a);i--)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef basic_string<int> BI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(random_device{}()); 
const ll mod=1000000007;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head

const int N=501000;
template<class T>
struct BIT {
	T c[N];
	int size;
	void init(int s) {
		size = s;
		for (int i = 1; i <= s; i++) c[i] = 0;
	}
	T query(int x) { // 1 ... x
		assert(x <= size);
		T s = 0;
		for (; x; x -= x & (-x)) {
			s = max(s, c[x]);
		}
		return s;
	}

	void modify(int x, T s) { // a[x] += s
		assert(x != 0);
		for (; x <= size; x += x & (-x)) {
			c[x] = max(c[x], s);
		}
	} 

};

int n,p[N],dp[N],pos[N],val[N];
VI pc[N];
BIT<int> c;

struct node {
	int fg,s;
}nd[4*N];
void upd(int p) {
	nd[p].s=min(nd[p+p].s,nd[p+p+1].s);
}
void setf(int p,int v) {
}
void build(int p,int l,int r) {
	nd[p].fg=0;
	if (l==r) {
		nd[p].s=1<<30;
	} else {
		int md=(l+r)>>1;
		build(p+p,l,md);
		build(p+p+1,md+1,r);
		upd(p);
	}
}
void push(int p) {
	if (nd[p].fg) {
		setf(p+p,nd[p].fg);
		setf(p+p+1,nd[p].fg);
		nd[p].fg=0;
	}
}
int query(int p,int l,int r,int tl,int tr) {
	if (tl==l&&tr==r) return nd[p].s;
	else {
		push(p);
		int md=(l+r)>>1;
		if (tr<=md) return query(p+p,l,md,tl,tr);
		else if (tl>md) return query(p+p+1,md+1,r,tl,tr);
		else return min(query(p+p,l,md,tl,md),query(p+p+1,md+1,r,md+1,tr));
	}
}

void change(int p,int l,int r,int x,int v) {
	if (p==1) {
		//printf("change %d %d\n",x,v);
	}
	if (l==r) nd[p].s=v;
	else {
		push(p);
		int md=(l+r)>>1;
		if (x<=md) change(p+p,l,md,x,v);
		else change(p+p+1,md+1,r,x,v);
		upd(p);
	}
}

void solve() {
	scanf("%d",&n);
	c.init(n);
	rep(i,1,n+1) pc[i].clear();
	rep(i,1,n+1) {
		scanf("%d",&p[i]);
		pos[p[i]]=i;
	}
	int M=0;
	per(i,1,n+1) {
		dp[i]=c.query(n+1-p[i])+1;
		M=max(M,dp[i]);
		c.modify(n+1-p[i],dp[i]);
		val[p[i]]=dp[i];
		pc[dp[i]].pb(p[i]);
	}
	VI v(p+1,p+n+1);
	VI ans;
	build(1,1,n);
	set<int> rem;
	rep(i,1,n+1) rem.insert(i);
	per(m,1,M+1) {
		for (auto x:pc[m]) if (rem.count(x)) change(1,1,n,pos[x],x);
		auto it=*rem.begin();
		change(1,1,n,pos[it],it);
		int ps=n;
		VI pc;
		while (ps>=1) {
			auto t=query(1,1,n,1,ps);
			if (t>n) break;
			//printf("!!! %d\n",t);
			rem.erase(t);
			pc.pb(t);
			change(1,1,n,pos[t],1<<30);
			ps=pos[t]-1;
		}
		reverse(all(pc));
		ans.insert(ans.end(),all(pc));
	}
	for (auto x:ans) printf("%d ",x);
	puts("");
}
int _;
int main() {
	for (scanf("%d",&_);_;_--) {
		solve();
	}
}

Submission Info

Compile Error

Main.cpp: In function ‘void setf(int, int)’:
Main.cpp:61:15: warning: unused parameter ‘p’ [-Wunused-parameter]
   61 | void setf(int p,int v) {
      |           ~~~~^
Main.cpp:61:21: warning: unused parameter ‘v’ [-Wunused-parameter]
   61 | void setf(int p,int v) {
      |                 ~~~~^
Main.cpp: In function ‘void solve()’:
Main.cpp:107:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  107 |         scanf("%d",&n);
      |         ~~~~~^~~~~~~~~
Main.cpp:111:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  111 |                 scanf("%d",&p[i]);
      |                 ~~~~~^~~~~~~~~~~~
Main.cpp: In function ‘int main()’:
Main.cpp:150:19: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  150 |         for (scanf("%d",&_);_;_--) {
      |              ~~~~~^~~~~~~~~

Judge Result