Submission #680992

#	Time	Username	Problem	Language	Result	Execution time	Memory
680992		arnold518	Financial Report (JOI21_financial)	C++17	0 / 100	4059 ms	17232 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;

struct SEG2
{
	pii tree[MAXN*4+10];
	void init(int node, int tl, int tr)
	{
		if(tl==tr)
		{
			tree[node]={A[tl], tl};
			return;
		}
		int mid=tl+tr>>1;
		init(node*2, tl, mid);
		init(node*2+1, mid+1, tr);
	}
	pii 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 pii(INF, INF);
		int mid=tl+tr>>1;
		return min(query(node*2, tl, mid, l, r), query(node*2+1, mid+1, tr, l, r));
	}
}seg2;

int dp[MAXN+10];

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

	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;

	for(auto it : V)
	{
		pii t=seg2.query(1, 1, N, it+1, it+D);
		if(t.first<=A[it]) uf.Union(t.second, it);
		t=seg2.query(1, 1, N, it-D, it-1);
		if(t.first<=A[it]) uf.Union(t.second, it);
		P[it]=uf.Find(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 member function 'void SEG2::init(int, int, int)':
Main.cpp:63:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   63 |   int mid=tl+tr>>1;
      |           ~~^~~
Main.cpp: In member function 'pii SEG2::query(int, int, int, int, int)':
Main.cpp:71:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   71 |   int mid=tl+tr>>1;
      |           ~~^~~
Main.cpp: In function 'int main()':
Main.cpp:80:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |  scanf("%d%d", &N, &D);
      |  ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:81:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |  for(int i=1; i<=N; i++) scanf("%d", &A[i]);
      |                          ~~~~~^~~~~~~~~~~~~

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