Submission #654164

#	Time	Username	Problem	Language	Result	Execution time	Memory
654164		aebov	Financial Report (JOI21_financial)	C++17	65 / 100	4065 ms	24376 KiB

Main

#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
#include<utility>
#include<queue>
#define ln (e-s+1)
#define md ((e+s)/2)
#define dm ((e+s)/2 + 1)
#define lc (id*2)
#define rc (id*2 + 1)
#define ll long long
#define F first
#define S second
#define pll pair<ll , ll>
#define pii pair<int, int>
#define pb push_back
using namespace std;

const int N = (int)3e5 + 5, inf = (int)1e9 + 7;
int n, d, a[N];
int dp[N];
vector<int> vct;
vector<int> pos[N];
int seg[N << 2];

void upd(int p,int x,int id = 1,int s = 1,int e = n){
	if(p < s || p > e)return;
	if(ln == 1){
		seg[id] = max(seg[id], x);
		return;
	}
	if(p>= s&&p <= md)upd( p, x, lc, s, md);
	if(p>=dm&&p <= e)upd( p, x, rc, dm, e);
	seg[id] = max(seg[lc], seg[rc]);
}
//void build(int k, int id = 1,int s)
int get(int l,int r,int id = 1,int s = 1,int  e = n){
	if(r < s|| l > e)return 0;
	if(l <= s && e <= r)return seg[id];
	return max(get( l, r, lc, s, md), get( l, r, rc, dm , e));
}
bool wef;
int few, ret, pd[N];
void sb(){
	// lis of seq is answer
	for(int i = 0 ; i <= n; i ++){
		for(auto ind : pos[i]) dp[ind] = get(1, ind-1) + 1;
		for(auto ind : pos[i]) upd(ind, dp[ind]), ret = max(ret, dp[ind]);
	}
	cout << ret << endl;
	exit(0);
}
void sb2(){
	int few = 0;
	priority_queue<int, vector<int>> q;

    for(int i = 1; i <= n; i ++){
        while(few && a[i] > a[dp[few]] )few --;
        pd[i] = dp[few] + 1;
        dp[++few] =i;
    }
    for(int i = n ; i ; i--){
        q.push(pd[i]);
        while(q.top() > i) q.pop();
        ret = max(ret, (int)q.size());
    }
	cout << ret << endl;
	exit(0);
}
int main(){
	//ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	scanf("%d%d", &n, &d);
	for(int i = 1; i <= n; i ++) scanf("%d", &a[i]), vct.pb(a[i]);
	sort(vct.begin(), vct.end()); unique( vct.begin(), vct.end());
	for(int i = 1; i <= n; i ++){
		a[i] = (lower_bound(vct.begin(), vct.end(), a[i]) - vct.begin());
		pos[a[i]].pb(i);
	//	upd(i, a[i]);
	}
	if(d == n)sb();
	if(d == 1)sb2();
	for(int i = 1; i <= n; i ++){
        dp[i] = wef = 1;
        few = 0;
		for(int j = i - 1 ; j ; j --){
            if(wef && a[j] < a[i]) dp[i] = max( dp[i], dp[j] + 1);
            (a[j] >= a[i])? few ++: few =0;
			if(few >= d) wef = 0;
        }
        ret = max(ret,dp[i]);
    }
    cout << ret <<endl;
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:73:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |  scanf("%d%d", &n, &d);
      |  ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:74:36: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |  for(int i = 1; i <= n; i ++) scanf("%d", &a[i]), vct.pb(a[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