Submission #1264840

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264840		herominhsteve	Volontiranje (COCI21_volontiranje)	C++20	110 / 110	325 ms	94448 KiB

Main

#include <bits/stdc++.h>
#define el '\n'
#define FNAME "nksgame"
#define allof(x) x.begin(),x.end()
#define allof1(x) x.begin()+1,x.end()
#define mset(x,n) memset(x,(n),sizeof(x))
using namespace std;
const long long MOD = (long long) 1e9+7;
template<class X,class Y> bool minimize(X &a,Y b){ if (a>b) {a=b; return true;} return false;}
template<class X,class Y> bool maximize(X &a,Y b){ if (a<b) {a=b; return true;} return false;}

void setup(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
	if (fopen(FNAME".inp","r")){
		freopen(FNAME".inp","r",stdin);
		freopen(FNAME".out","w",stdout);
	}
}

const int MAXN = 1e6 + 1;

template<typename T>
struct FenwickTree{
	int n;
	vector<T> bit;
	FenwickTree(int N=0){
		n=N;
		if (n>0){
			bit.resize(n+1,0);
		}
	}
	void update(int node,T val){
		while (node<=n){
			maximize(bit[node],val);
			node += (node & -node);
		}
	}
	T getVal(int node){
		T res=0;
		while (node>0){
			maximize(res,bit[node]);
			node -= (node & -node);
		}
		return res;
	}
};

int n;
vector<int> a;

// ! e[pos] stores ending indices of LIS length pos + 1
vector<int> e[MAXN];
int len;

void init(){
	cin>>n;
	a.resize(n);
	vector<int> org(n);
	for (int &x:org) cin>>x;
	vector<int> compress(allof(org));
	sort(allof(compress));
	compress.resize(unique(allof(compress))-compress.begin());
	for (int i=0;i<n;i++) a[i] = lower_bound(allof(compress),org[i]) - compress.begin() + 1;
}

void buildLIS(){
	FenwickTree<int> bit(n);
	for (int i=0;i<n;i++){
		int pos = bit.getVal(a[i]-1);
		e[pos].push_back(i);
		bit.update(a[i],pos+1);
	}
	len = bit.getVal(n);
	for (int i=0;i<len;i++){
		reverse(allof(e[i]));
	}
}

void sol(){
	buildLIS();
	vector<vector<int>> res;
	vector<int> st;
	while (1+1==2){
		if (st.empty()){
			if (e[0].empty()) break;
			st.push_back(e[0].back());
			e[0].pop_back();
		} else if ((int)st.size() == len){
			res.push_back(st);
			st.clear();
		} else{
			int curLen = st.size();
			int curID = st.back();
			while (!e[curLen].empty() and e[curLen].back() < curID) 
				e[curLen].pop_back();
			if (e[curLen].empty() or a[curID] > a[e[curLen].back()])
				st.pop_back();
			else{
				st.push_back(e[curLen].back());
				e[curLen].pop_back();
			}
		}
	}
	cout<<res.size()<<" "<<len<<el;
	for (vector<int> &v : res){
		for (int x : v) cout<<x+1<<" ";
		cout<<el;
	}
}

int main(){
    setup();
    init();
    sol();
}

Compilation message (stderr)

Main.cpp: In function 'void setup()':
Main.cpp:16:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |                 freopen(FNAME".inp","r",stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:17:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |                 freopen(FNAME".out","w",stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 40 / 40
• Subtask 3: 60 / 60