Submission #654169

#	Time	Username	Problem	Language	Result	Execution time	Memory
654169		nolimiya	Financial Report (JOI21_financial)	C++14	65 / 100	345 ms	44372 KiB

Main

#include <bits/stdc++.h>
#include <math.h>
//in the name of god,aka allah
//**gray sety orz**
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")
using namespace std;
#define pi pair<long long , long long>
#define pii pair<long long , pair<long long , long long>>
const int maxm = 3e5 + 4;
const long long mod = 1e9 + 7 ;
typedef long long ll;
ll l,r,mid;
ll n,m;
ll dis[maxm] , sum[maxm];
bool isval(int mid){
    //cout << mid <<" " << mid*mid-mid <<endl;
    if (((mid-1)*mid)/2 < m) return 0;
    return 1;
}
ll darage[maxm] , ss , mm;
queue<int> q;
vector<pi> g[maxm] , z[maxm];
ll sath[maxm];
bool vis[maxm] , gos[maxm];
int pedaret[maxm];
ll get_par(ll v){
    if (pedaret[v]==v) return v;
    return pedaret[v] = get_par(pedaret[v]);
}
void merge(ll r , ll q){
    if (get_par(r)!=get_par(q))l+=max(darage[r],darage[q])*1ll*sath[r]*1ll*sath[q];
    r = get_par(r) , q = get_par(q);
    if (r!=q){
        if (sath[r]<sath[q]) swap(r,q);
        pedaret[q] = r;
        sath[r] += sath[q];
    }
    return ;
}
ll pars1[maxm] , pars2[maxm];
vector<ll> se[maxm];
set<ll> st;
int sq = 500;
int rp[maxm];
pair<int,int> w[maxm];
ll dp[maxm];
ll rw[2000][2000];
map<ll,ll> mp;
void get(int x){
    ll ans = 0;
    while (1){
        ans+=w[x].first;
       // if (x==w[x].second) break;
        x = w[x].second;
        if (x==w[x].second) break;
        //cout<<x<<" "<<ans<<endl;
        //cout<<w[x].first<<" "<<w[x].second<<" "<<x<<endl;
    }
    cout<<x<<' '<<ans+1<<'\n';
}
void upd(int x ,int y){
    pedaret[x] = y;
    int t=darage[x];
    for (int j=rp[t+1]-1; j>=rp[t]; j--){
        //cout<<j<<"hi"<<endl;
        if (j+pedaret[j]>n) w[j] = {0,j};
        else{
            if (j+pedaret[j]>=rp[t+1]) w[j] = {1,j+pedaret[j]};
            else w[j] = {w[j+pedaret[j]].first+1,w[j+pedaret[j]].second};
        }
    }
    //cout<<endl;
}
void solve(){
    for(int i=0; i<=n; i++)
    for(int j=0; j<=n; j++) rw[i][j]=-mod;
    rw[0][0]=0;
    for(int i=0; i<n; i++){
        if(i) rw[i][pedaret[i]]=max(rw[i][pedaret[i]],1ll);
        for(int j=0; j<=n; j++){
            for(int k=i+1; k<=i+m; k++){
                if(k<=n){
                    rw[k][max(pedaret[k],j)]=max(rw[k][max(pedaret[k],j)],rw[i][j]+(pedaret[k]>j));
                }
            }
        }
    }
    for(int j=0; j<=n; j++) mid = max(mid, rw[n][j]);
    cout<<mid;
}
void solve1(){
    for(int i=1; i<=n; i++){
        dp[i] = 1;
        bool ok=1;
        r = 0;
        for(int j=i-1; j>=1; j--){
            if(ok && pedaret[j]<pedaret[i]) dp[i]=max(dp[i],dp[j]+1);
            if(pedaret[j]>=pedaret[i]) r++;
            else r=0;
            if(r>=m) ok=0;
        }
        mid =max(mid,dp[i]);
    }
    cout<<mid<<endl;
}
void solve2(){
    priority_queue<int>ts;
    for(int i=1; i<=n; i++){
        while(ss && pedaret[i]>pedaret[dp[ss]]) ss--;
        rp[i] =dp[ss]+1;
        dp[++ss] =i;
    }
    for(int i=n; i>0; i--){
        ts.push(rp[i]);
        while(ts.top()>i) ts.pop();
        mm=max(mm,(ll)ts.size());
    }
    cout<<mm<<endl;
}
int LongestIncreasingSubsequenceLength(std::vector<int>& v){
    if (v.size() == 0) return 0;
    std::vector<int> tail(v.size(), 0);
    int length = 1;
    tail[0] = v[0];
    for (int i = 1; i < v.size(); i++) {
        auto b = tail.begin(), e = tail.begin() + length;
        auto it = lower_bound(b, e, v[i]);
        if (it == tail.begin() + length)
            tail[length++] = v[i];
        else
            *it = v[i];
    }
 
    return length;
}
vector<int >vec;
void solve3(){
    cout<<LongestIncreasingSubsequenceLength(vec)<<endl;
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin >>n>>m;
    for (int i=1; i<=n; i++) cin>>pedaret[i],vec.push_back(pedaret[i]);
    for (int i=1; i<=n; i++) st.insert(pedaret[i]);
    for (int j:st) darage[++l]=j;
    for (int i=1; i<=n; i++) pedaret[i]=lower_bound(darage+1,darage+l+1,pedaret[i])-darage;
    if (2000>=n){
        solve();
        return 0;
    }
    if (n<10000){
        solve1();
        return 0;
    }
    if (m==1){
        solve2();
        return 0;
    }
    if (m==n){
        solve3();
        return 0;
    }
}

Compilation message (stderr)

Main.cpp:5: warning: ignoring '#pragma comment ' [-Wunknown-pragmas]
    5 | #pragma comment(linker, "/stack:200000000")
      | 
Main.cpp: In function 'int LongestIncreasingSubsequenceLength(std::vector<int>&)':
Main.cpp:153:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  153 |     for (int i = 1; i < v.size(); i++) {
      |                     ~~^~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 20 / 20
• Subtask 4: 12 / 12
• Subtask 5: 5 / 5
• Subtask 6: 0 / 35