oj.uz

Submission #556700

# Submission time Handle Problem Language Result Execution time Memory
556700 2022-05-03T17:26:06 Z new_acc Volontiranje (COCI21_volontiranje) C++14
0 / 110
 30 ms 47416 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);
    while(seg[curr][1]<ind and rek(curr-1,pom[curr][q-1])==-1){
        upd2(curr,q,INFi);
        q=Query2(curr,ind);
    }
    if(t[pom[curr][q-1]]>t[ind]) return -1;
    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 27 ms 47316 KB Output is correct
2 Correct 24 ms 47316 KB Output is correct
3 Correct 30 ms 47296 KB Output is correct
4 Correct 24 ms 47364 KB Output is correct
5 Correct 24 ms 47336 KB Output is correct
6 Correct 23 ms 47296 KB Output is correct
7 Correct 23 ms 47328 KB Output is correct
8 Correct 23 ms 47348 KB Output is correct
9 Correct 23 ms 47320 KB Output is correct
10 Correct 23 ms 47360 KB Output is correct
11 Correct 25 ms 47316 KB Output is correct
12 Correct 23 ms 47316 KB Output is correct
13 Correct 25 ms 47292 KB Output is correct
14 Correct 23 ms 47360 KB Output is correct
15 Correct 23 ms 47356 KB Output is correct
16 Correct 24 ms 47240 KB Output is correct
17 Incorrect 23 ms 47416 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 47316 KB Output is correct
2 Correct 24 ms 47316 KB Output is correct
3 Correct 30 ms 47296 KB Output is correct
4 Correct 24 ms 47364 KB Output is correct
5 Correct 24 ms 47336 KB Output is correct
6 Correct 23 ms 47296 KB Output is correct
7 Correct 23 ms 47328 KB Output is correct
8 Correct 23 ms 47348 KB Output is correct
9 Correct 23 ms 47320 KB Output is correct
10 Correct 23 ms 47360 KB Output is correct
11 Correct 25 ms 47316 KB Output is correct
12 Correct 23 ms 47316 KB Output is correct
13 Correct 25 ms 47292 KB Output is correct
14 Correct 23 ms 47360 KB Output is correct
15 Correct 23 ms 47356 KB Output is correct
16 Correct 24 ms 47240 KB Output is correct
17 Incorrect 23 ms 47416 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 47316 KB Output is correct
2 Correct 24 ms 47316 KB Output is correct
3 Correct 30 ms 47296 KB Output is correct
4 Correct 24 ms 47364 KB Output is correct
5 Correct 24 ms 47336 KB Output is correct
6 Correct 23 ms 47296 KB Output is correct
7 Correct 23 ms 47328 KB Output is correct
8 Correct 23 ms 47348 KB Output is correct
9 Correct 23 ms 47320 KB Output is correct
10 Correct 23 ms 47360 KB Output is correct
11 Correct 25 ms 47316 KB Output is correct
12 Correct 23 ms 47316 KB Output is correct
13 Correct 25 ms 47292 KB Output is correct
14 Correct 23 ms 47360 KB Output is correct
15 Correct 23 ms 47356 KB Output is correct
16 Correct 24 ms 47240 KB Output is correct
17 Incorrect 23 ms 47416 KB Output isn't correct
18 Halted 0 ms 0 KB -