Submission #872970

#	Time	Username	Problem	Language	Result	Execution time	Memory
872970		tsumondai	Volontiranje (COCI21_volontiranje)	C++14	110 / 110	206 ms	109140 KiB

Main

/*
Tím dãy con tăng dài nhất và số lượng các dãy con đó cũng như liệt kê các chỉ số của chúng!
*/

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, r, l) for(int i = r; i >= l; i--)
#define __TIME  (1.0 * clock() / CLOCKS_PER_SEC)

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
 
const int N = 1e6 + 5;
 
const int oo = 1e18, mod = 1e9 + 7;
 
int n, m, k, a[N];
vector<int> v[N], r, st;
vector<vector<int>> out;

// subtask 1: 

void build_LIS() {
	foru(i,1,n) {
		int pos=lower_bound(r.begin(), r.end(), a[i])-r.begin();
		if (pos==r.size()) {
			r.pb(a[i]);
		} else {
			r[pos]=a[i];
		}
		v[pos].pb(i);
	}
	foru(i,0,r.size()-1) {
		reverse(v[i].begin(), v[i].end());
	}
}

void process() {
	while (1) {
		if (st.size()==0) {
			if (v[0].empty()) break;
			int pos=v[0].back();
			v[0].pop_back();
			st.pb(pos);
		} else if (st.size()==r.size()) {
			out.pb(st);
			st.clear();
		} else {
			int k=st.size();
			int curr=st.back();
			while (!v[k].empty() && v[k].back() < curr) v[k].pop_back();
			if (v[k].empty() || a[curr] > a[v[k].back()]) {
				st.pop_back();
			} else {
				int pos=v[k].back();
				v[k].pop_back();
				st.push_back(pos);
			}
		}
	}
}

void trace() {
	cout << out.size() << ' ' << r.size() << '\n';
	foru(i,0,out.size()-1) {
		for (auto x: out[i]) cout << x << ' ';
		cout << '\n';
	}
}



signed main() {
    cin.tie(0)->sync_with_stdio(false);
    //freopen(".inp", "r", stdin);
    //freopen(".out", "w", stdout);
    cin >> n;
    foru(i,1,n) cin >> a[i];
	build_LIS();
    process();
    trace();
    cerr << "Time elapsed: " << __TIME << " s.\n";
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void build_LIS()':
Main.cpp:34:10: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |   if (pos==r.size()) {
      |       ~~~^~~~~~~~~~
Main.cpp:13:40: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 | #define foru(i, l, r) for(int i = l; i <= r; i++)
......
   41 |  foru(i,0,r.size()-1) {
      |       ~~~~~~~~~~~~~~                    
Main.cpp:41:2: note: in expansion of macro 'foru'
   41 |  foru(i,0,r.size()-1) {
      |  ^~~~
Main.cpp: In function 'void trace()':
Main.cpp:13:40: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 | #define foru(i, l, r) for(int i = l; i <= r; i++)
......
   73 |  foru(i,0,out.size()-1) {
      |       ~~~~~~~~~~~~~~~~                  
Main.cpp:73:2: note: in expansion of macro 'foru'
   73 |  foru(i,0,out.size()-1) {
      |  ^~~~

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