Submission #546578

#	Time	Username	Problem	Language	Result	Execution time	Memory
546578		nafis_shifat	Financial Report (JOI21_financial)	C++14	100 / 100	709 ms	39740 KiB

Main

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;
const int mxn=3e5+5;
const int inf=1e9;
int n, D;
int a[mxn];
struct segtree {
	int tree[4 * mxn] = {};
	int pref[4 * mxn] = {};
	int suf[4 * mxn] = {};

	void build(int node,int b,int e) {
		if(b==e) {
			tree[node] = 1;
			suf[node] = 1;
			pref[node] = 1;
			return;
		}
		int mid=b+e>>1;
		int left=node<<1;
		int right=left|1;

		build(left,b,mid);
		build(right,mid+1,e);
		tree[node] = pref[node] = suf[node] = e - b + 1;

	}


	void update(int node,int b,int e,int p) {
		if(e<p || b>p)return;
		if(b == e) {
			tree[node] = 0;
			suf[node] = 0;
			pref[node] = 0;
			return;
		}
		

		int mid=b+e>>1;
		int left=node<<1;
		int right=left|1;

		update(left,b,mid,p);
		update(right,mid+1,e,p);

		tree[node] = max({tree[left], tree[right], suf[left] + pref[right]});
		suf[node] = suf[right];
		pref[node] = pref[left];

		if(suf[right] == e - mid) suf[node] += suf[left];
		if(pref[left] == mid - b + 1) pref[node] += pref[right];

	}

	int query(int node, int b, int e, int p) {
		if(b > p) return -1;
		if(e <= p && suf[node] >= D) {
			return e;
		}

		if(tree[node] < D) return -1;


		int mid = b + e >> 1;
		int left = node << 1;
		int right = left | 1;

		if(p <= mid) return query(left, b, mid, p);

		int vr = query(right, mid + 1, e, p);
		if(vr != -1) return vr;

		if(mid + pref[right] <= p && suf[left] + pref[right] >= D) return mid + pref[right];
	    if(mid + pref[right] > p && p - mid + suf[left] >= D) return p;

		return query(left, b, mid, p);
	}
} st;


struct sgtree {
	int tree[4*mxn] = {};

	void update(int node,int b,int e,int p,int v) {
		if(e<p || b>p)return;
		if(b == e) {
			tree[node] = v;
			return;
		}

		int mid=b+e>>1;
		int left=node<<1;
		int right=left|1;

		update(left,b,mid,p,v);
		update(right,mid+1,e,p,v);
		tree[node]=max(tree[left],tree[right]);
	}

	int query(int node, int b, int e, int l, int r) {
		if(e < l || b > r) return 0;
		if(b >= l && e <= r) return tree[node];
		int mid=b+e>>1;
		int left=node<<1;
		int right=left|1;
		return max(query(left, b, mid, l, r), query(right, mid + 1, e, l, r));
	}
} rmq;
int main() {
	cin >> n >> D;
	vector<int> v;
	vector<int> con[n + 1];
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
		v.push_back(a[i]);
	}

	sort(v.begin(),v.end());

	v.erase(unique(v.begin(), v.end()), v.end());

	for(int i = 1; i <= n; i++) {
		a[i] = lower_bound(v.begin(), v.end(), a[i]) - v.begin() + 1;
		con[a[i]].push_back(i);
	}

	st.build(1, 1, n);

	int dp[n + 1] = {};
	int ans = 0;

	for(int x = 1; x <= n; x++) {
		for(int i : con[x]) {
			int p = st.query(1, 1, n, i - 1);
			if(p == -1) dp[i] = rmq.query(1, 1, n, 1, i - 1) + 1;
			else dp[i] = rmq.query(1, 1, n, p, i - 1) + 1;
		}

		for(int i : con[x]) {
			st.update(1, 1, n, i);
			rmq.update(1, 1, n, i, dp[i]);
			ans = max(ans, dp[i]);
		}
	}

	cout<<ans<<endl;




	
}

Compilation message (stderr)

Main.cpp: In member function 'void segtree::build(int, int, int)':
Main.cpp:21:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   21 |   int mid=b+e>>1;
      |           ~^~
Main.cpp: In member function 'void segtree::update(int, int, int, int)':
Main.cpp:42:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 |   int mid=b+e>>1;
      |           ~^~
Main.cpp: In member function 'int segtree::query(int, int, int, int)':
Main.cpp:67:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   67 |   int mid = b + e >> 1;
      |             ~~^~~
Main.cpp: In member function 'void sgtree::update(int, int, int, int, int)':
Main.cpp:94:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   94 |   int mid=b+e>>1;
      |           ~^~
Main.cpp: In member function 'int sgtree::query(int, int, int, int, int)':
Main.cpp:106:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  106 |   int mid=b+e>>1;
      |           ~^~

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