oj.uz

답안 #556694

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
556694 2022-05-03T17:06:17 Z new_acc Volontiranje (COCI21_volontiranje) C++14
0 / 110
 23 ms 47276 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()<<"\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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 23 ms 47276 KB length of the longest increasing subsequence doesn't match
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 23 ms 47276 KB length of the longest increasing subsequence doesn't match
2 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 23 ms 47276 KB length of the longest increasing subsequence doesn't match
2 Halted 0 ms 0 KB -