oj.uz

Submission #556699

# Submission time Handle Problem Language Result Execution time Memory
556699 2022-05-03T17:24:43 Z new_acc Volontiranje (COCI21_volontiranje) C++14
0 / 110
 28 ms 47368 KB 
#include<bits/stdc++.h>
#define fi first
#define se second
#define pitem item*
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=1e6+10;
const int SS=1<<19;
const int INFi=2e9;
const ll INFl=1e13;
const ll mod2=998244353;
const ll mod=1e9+7;
const ll mod3=1000696969;
const ll p=70032301;
const ull p2=913;
const int L=20;
int t[N],num[N],seg2[N],dp[N];
vi seg[N],pom[N],c;
void upd(int a,int b){
    for(a+=SS;a>0;a>>=1) seg2[a]=max(seg2[a],b);
}
int Query(int a,int b){
    int res=0;
    for(a+=SS-1,b+=SS+1;(a>>1)!=(b>>1);a>>=1,b>>=1){
        if(!(a&1)) res=max(res,seg2[a+1]);
        if(b&1) res=max(res,seg2[b-1]);
    }
    return res;
}
void upd2(int x,int a,int b){
    a+=num[x],seg[x][a]=b;
    for(a>>=1;a>0;a>>=1) seg[x][a]=min(seg[x][(a<<1)],seg[x][(a<<1)+1]);
}
int Query2(int curr,int x,int v=1){
    if(v>num[curr]) return v-num[curr];
    if(seg[curr][(v<<1)+1]<=x) return Query2(curr,x,(v<<1)+1);
    else return Query2(curr,x,(v<<1));
}
int rek(int curr,int ind){
    if(curr==0) return 1;
    int q=Query2(curr,ind);
    if(t[pom[curr][q-1]]>t[ind]) return -1;
    while(seg[curr][1]<ind and rek(curr-1,pom[curr][q-1])==-1){
        upd2(curr,q,INFi);
        q=Query2(curr,ind);
    }
    if(seg[curr][1]>ind) return -1;
    c.push_back(pom[curr][q-1]);
    upd2(curr,q,INFi);
    return 1;
}
void solve(){
    int n,maxi=0;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>t[i];
        dp[i]=Query(1,t[i])+1;
        upd(t[i],dp[i]);
        pom[dp[i]].push_back(i);
        maxi=max(maxi,dp[i]);
    }
    t[n+1]=n+1;
    for(int i=1;i<=maxi;i++){
        int curr=1;
        while(curr<=pom[i].size()) curr<<=1;
        for(int k=1;k<=(curr<<1)+5;k++) seg[i].push_back(INFi);
        num[i]=curr;
        for(int j=0;j<pom[i].size();j++) upd2(i,j+1,pom[i][j]);
    }
    vector<vi>ans;
    while(rek(maxi,n+1)>0) ans.push_back(c),c.clear();
    cout<<ans.size()<<" "<<maxi<<"\n";
    for(auto u:ans){
        for(auto xd:u) cout<<xd<<" ";
        cout<<"\n";
    }
}
int main(){
    ios_base::sync_with_stdio(0),cin.tie(0);
    int tt=1;
    while(tt--) solve();
}

Compilation message

Main.cpp: In function 'void solve()':
Main.cpp:68:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |         while(curr<=pom[i].size()) curr<<=1;
      |               ~~~~^~~~~~~~~~~~~~~
Main.cpp:71:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |         for(int j=0;j<pom[i].size();j++) upd2(i,j+1,pom[i][j]);
      |                     ~^~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47308 KB Output is correct
2 Correct 22 ms 47256 KB Output is correct
3 Correct 23 ms 47240 KB Output is correct
4 Correct 23 ms 47308 KB Output is correct
5 Correct 23 ms 47284 KB Output is correct
6 Correct 25 ms 47276 KB Output is correct
7 Correct 28 ms 47284 KB Output is correct
8 Correct 24 ms 47296 KB Output is correct
9 Correct 25 ms 47316 KB Output is correct
10 Correct 24 ms 47352 KB Output is correct
11 Correct 24 ms 47316 KB Output is correct
12 Correct 24 ms 47340 KB Output is correct
13 Correct 22 ms 47280 KB Output is correct
14 Correct 24 ms 47360 KB Output is correct
15 Correct 23 ms 47268 KB Output is correct
16 Correct 24 ms 47368 KB Output is correct
17 Incorrect 24 ms 47336 KB Subsequence increasing
18 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47308 KB Output is correct
2 Correct 22 ms 47256 KB Output is correct
3 Correct 23 ms 47240 KB Output is correct
4 Correct 23 ms 47308 KB Output is correct
5 Correct 23 ms 47284 KB Output is correct
6 Correct 25 ms 47276 KB Output is correct
7 Correct 28 ms 47284 KB Output is correct
8 Correct 24 ms 47296 KB Output is correct
9 Correct 25 ms 47316 KB Output is correct
10 Correct 24 ms 47352 KB Output is correct
11 Correct 24 ms 47316 KB Output is correct
12 Correct 24 ms 47340 KB Output is correct
13 Correct 22 ms 47280 KB Output is correct
14 Correct 24 ms 47360 KB Output is correct
15 Correct 23 ms 47268 KB Output is correct
16 Correct 24 ms 47368 KB Output is correct
17 Incorrect 24 ms 47336 KB Subsequence increasing
18 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47308 KB Output is correct
2 Correct 22 ms 47256 KB Output is correct
3 Correct 23 ms 47240 KB Output is correct
4 Correct 23 ms 47308 KB Output is correct
5 Correct 23 ms 47284 KB Output is correct
6 Correct 25 ms 47276 KB Output is correct
7 Correct 28 ms 47284 KB Output is correct
8 Correct 24 ms 47296 KB Output is correct
9 Correct 25 ms 47316 KB Output is correct
10 Correct 24 ms 47352 KB Output is correct
11 Correct 24 ms 47316 KB Output is correct
12 Correct 24 ms 47340 KB Output is correct
13 Correct 22 ms 47280 KB Output is correct
14 Correct 24 ms 47360 KB Output is correct
15 Correct 23 ms 47268 KB Output is correct
16 Correct 24 ms 47368 KB Output is correct
17 Incorrect 24 ms 47336 KB Subsequence increasing
18 Halted 0 ms 0 KB -