oj.uz

Submission #556695

# Submission time Handle Problem Language Result Execution time Memory
556695 2022-05-03T17:07:36 Z new_acc Volontiranje (COCI21_volontiranje) C++14
0 / 110
 26 ms 47420 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(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]);
    }
    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:66:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |         while(curr<=pom[i].size()) curr<<=1;
      |               ~~~~^~~~~~~~~~~~~~~
Main.cpp:69:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |         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 47316 KB Output is correct
2 Correct 23 ms 47364 KB Output is correct
3 Correct 24 ms 47316 KB Output is correct
4 Correct 22 ms 47316 KB Output is correct
5 Correct 26 ms 47420 KB Output is correct
6 Correct 23 ms 47352 KB Output is correct
7 Correct 24 ms 47272 KB Output is correct
8 Correct 23 ms 47292 KB Output is correct
9 Correct 23 ms 47316 KB Output is correct
10 Correct 23 ms 47248 KB Output is correct
11 Correct 23 ms 47348 KB Output is correct
12 Correct 24 ms 47276 KB Output is correct
13 Correct 23 ms 47316 KB Output is correct
14 Correct 23 ms 47292 KB Output is correct
15 Correct 22 ms 47316 KB Output is correct
16 Correct 23 ms 47336 KB Output is correct
17 Incorrect 26 ms 47256 KB Subsequence increasing
18 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47316 KB Output is correct
2 Correct 23 ms 47364 KB Output is correct
3 Correct 24 ms 47316 KB Output is correct
4 Correct 22 ms 47316 KB Output is correct
5 Correct 26 ms 47420 KB Output is correct
6 Correct 23 ms 47352 KB Output is correct
7 Correct 24 ms 47272 KB Output is correct
8 Correct 23 ms 47292 KB Output is correct
9 Correct 23 ms 47316 KB Output is correct
10 Correct 23 ms 47248 KB Output is correct
11 Correct 23 ms 47348 KB Output is correct
12 Correct 24 ms 47276 KB Output is correct
13 Correct 23 ms 47316 KB Output is correct
14 Correct 23 ms 47292 KB Output is correct
15 Correct 22 ms 47316 KB Output is correct
16 Correct 23 ms 47336 KB Output is correct
17 Incorrect 26 ms 47256 KB Subsequence increasing
18 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47316 KB Output is correct
2 Correct 23 ms 47364 KB Output is correct
3 Correct 24 ms 47316 KB Output is correct
4 Correct 22 ms 47316 KB Output is correct
5 Correct 26 ms 47420 KB Output is correct
6 Correct 23 ms 47352 KB Output is correct
7 Correct 24 ms 47272 KB Output is correct
8 Correct 23 ms 47292 KB Output is correct
9 Correct 23 ms 47316 KB Output is correct
10 Correct 23 ms 47248 KB Output is correct
11 Correct 23 ms 47348 KB Output is correct
12 Correct 24 ms 47276 KB Output is correct
13 Correct 23 ms 47316 KB Output is correct
14 Correct 23 ms 47292 KB Output is correct
15 Correct 22 ms 47316 KB Output is correct
16 Correct 23 ms 47336 KB Output is correct
17 Incorrect 26 ms 47256 KB Subsequence increasing
18 Halted 0 ms 0 KB -