# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
658389 | sam571128 | Volontiranje (COCI21_volontiranje) | C++17 | 290 ms | 116652 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0);
#define int long long
using namespace std;
const int N = 1e6+5;
vector<int> num[N];
vector<vector<int>> ans;
int arr[N], dp[N];
signed main(){
fastio
int n;
cin >> n;
for(int i = 1; i <= n; i++){
cin >> arr[i];
}
vector<int> lis;
for(int i = 1; i <= n; i++){
int idx = lower_bound(lis.begin(),lis.end(),arr[i])-lis.begin();
if(idx==lis.size()) lis.push_back(arr[i]);
else lis[idx] = arr[i];
dp[i] = idx+1;
num[idx+1].push_back(i);
}
int m = lis.size();
for(int i = 1; i <= m; i++){
reverse(num[i].begin(),num[i].end());
}
vector<int> tmp;
int now = 1, idx = n+1;
while(true){
tmp.clear();
for(int i = 1; i <= m; i++){
while(!num[i].empty()){
if(!tmp.empty()&&num[i].back() < tmp.back()) num[i].pop_back();
else if(!tmp.empty() && arr[num[i].back()] < arr[tmp.back()]){
tmp.pop_back();
i -= 2;
goto popped;
}
else{
tmp.push_back(num[i].back());
num[i].pop_back();
break;
}
}
if(tmp.size() < i){
goto done;
}
popped:;
}
ans.push_back(tmp);
}
done:;
cout << ans.size() << " " << m << "\n";
for(auto v : ans){
for(auto x : v){
cout << x << " ";
}
cout << "\n";
}
}
/*
*/
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |