Submission #680989

#	Time	Username	Problem	Language	Result	Execution time	Memory
680989		arnold518	Financial Report (JOI21_financial)	C++17	100 / 100	2066 ms	28088 KiB

Main

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 3e5;
const int INF = 1e9+7;

int N, D;
int A[MAXN+10], P[MAXN+10];

struct UF
{
	int par[MAXN+10];
	int Find(int x)
	{
		if(x==par[x]) return x;
		return Find(par[x]);
	}
	void Union(int x, int y)
	{
		x=Find(x); y=Find(y);
		par[x]=y;
	}
}uf;

struct SEG
{
	int tree[MAXN*4+10];
	SEG()
	{
		fill(tree, tree+MAXN*4+10, -INF);
	}
	void update(int node, int tl, int tr, int p, int q)
	{
		tree[node]=max(tree[node], q);
		if(tl==tr) return;
		int mid=tl+tr>>1;
		if(p<=mid) update(node*2, tl, mid ,p, q);
		else update(node*2+1, mid+1, tr, p, q);
	}
	int query(int node, int tl, int tr, int l, int r)
	{
		if(l<=tl && tr<=r) return tree[node];
		if(r<tl || tr<l) return -INF;
		int mid=tl+tr>>1;
		return max(query(node*2, tl, mid, l, r), query(node*2+1, mid+1, tr, l, r));
	}
}seg;

int dp[MAXN+10];

int main()
{
	scanf("%d%d", &N, &D);
	for(int i=1; i<=N; i++) scanf("%d", &A[i]);

	vector<int> V;
	for(int i=1; i<=N; i++) V.push_back(i);
	sort(V.begin(), V.end(), [&](const int &p, const int &q)
	{
		if(A[p]==A[q]) return p>q;
		return A[p]<A[q];
	});
	
	for(int i=1; i<=N; i++) uf.par[i]=i;

	set<int> S;
	for(auto it : V)
	{
		auto jt=S.lower_bound(it);
		if(jt!=S.end() && *jt-it<=D) uf.Union(it, *jt);
		if(jt!=S.begin() && it-*prev(jt)<=D) uf.Union(*prev(jt), it);
		P[it]=uf.Find(it);
		S.insert(it);
	}

	int ans=1;

	sort(V.begin(), V.end(), [&](const int &p, const int &q)
	{
		if(A[p]==A[q]) return p<q;
		return A[p]>A[q];
	});

	for(auto it : V)
	{
		dp[it]=seg.query(1, 1, N, it, P[it]+D)+1;
		if(P[it]==N) dp[it]=max(dp[it], 1);
		seg.update(1, 1, N, it, dp[it]);
		ans=max(ans, dp[it]);
	}

	printf("%d\n", ans);
}

Compilation message (stderr)

Main.cpp: In member function 'void SEG::update(int, int, int, int, int)':
Main.cpp:40:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   40 |   int mid=tl+tr>>1;
      |           ~~^~~
Main.cpp: In member function 'int SEG::query(int, int, int, int, int)':
Main.cpp:48:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   48 |   int mid=tl+tr>>1;
      |           ~~^~~
Main.cpp: In function 'int main()':
Main.cpp:57:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |  scanf("%d%d", &N, &D);
      |  ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:58:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |  for(int i=1; i<=N; i++) scanf("%d", &A[i]);
      |                          ~~~~~^~~~~~~~~~~~~

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