Submission #654119

#	Time	Username	Problem	Language	Result	Execution time	Memory
654119		nolimiya	Financial Report (JOI21_financial)	C++14	14 / 100	51 ms	24244 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 = 1e5 + 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[maxm][maxm];
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 solve1(){
    for(int i=1; i<=n; i++){
        dp[i] = 1;
        bool ok=1;
        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 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];
    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 (n<10000){
        solve1();
        return 0;
    }
    if (m==1){
        solve2();
        return 0;
    }
}

Compilation message (stderr)

Main.cpp:5: warning: ignoring '#pragma comment ' [-Wunknown-pragmas]
    5 | #pragma comment(linker, "/stack:200000000")
      |

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