Submission #1308388

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308388		thuhienne	Mizuyokan 2 (JOI23_mizuyokan2)	C++20	28 / 100	4090 ms	7204 KiB

mizuyokan2

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

using ll = long long;

#define re exit(0);

const int maxn = 250009;

int fen[maxn];

void update(int pos,int val) {
	for (;pos <= 250003;pos += (pos & -pos)) fen[pos] = max(fen[pos],val);
}
int get(int pos) {
	int ret = -1e9;
	for (;pos;pos -= (pos & -pos)) ret = max(ret,fen[pos]);
	return ret;
}

int n,d[maxn];

int dp[maxn];
ll pref[maxn];

priority_queue <pair <ll,int>,vector <pair <ll,int>>,greater <pair <ll,int>>> pq;

int calc(vector <int> & arr) {
	
	arr.insert(arr.begin(),0);
	arr.push_back(0);
	int n = (int)arr.size() - 1;
	
	while (pq.size()) pq.pop();
	memset(fen,-0x3f,sizeof(fen));
	
	for (int i = 1;i <= n;i++) pref[i] = pref[i - 1] + arr[i];

	dp[0] = 0;
	pq.push({0,0});
	
	dp[1] = 1;
	pq.push({pref[1] + arr[1],1});
	
	for (int i = 2;i <= n;i++) {
		
		while (pq.size() && pq.top().first < pref[i - 1]) {
			int pos = pq.top().second;pq.pop();
			update(pos + 1,dp[pos]);
		}
		
		int l = 0,r = i - 2;
		while (l <= r) {
			int mid = (l + r) >> 1;
			if (pref[i - 1] - pref[mid] > arr[i]) l = mid + 1;
			else r = mid - 1; 
		}
		
		dp[i] = get(r + 1) + 2;
//		for (int j = i - 1;j >= 1;j--) {
//			if (pref[i - 1] - pref[j - 1] > arr[i] && pref[i - 1] - pref[j - 1] > arr[j - 1]) {
//				dp[i] = max(dp[i],dp[j - 1] + 2);
//			}
//		}
		
		pq.push({pref[i] + arr[i],i});
	}
	
	return max(dp[n - 1],dp[n] - 1);
}

void solve() {
	int x,y,a,b;cin >> x >> y >> a >> b;
	d[x] = y;
	
	vector <int> temp;
	for (int i = a + 1;i <= b;i++) temp.push_back(d[i]);
	
	cout << calc(temp) << '\n';
	
}

int main() {
  ios_base::sync_with_stdio(0);cin.tie(nullptr);

	cin >> n;
	for (int i = 1;i <= n;i++) cin >> d[i];
	
	int q;cin >> q;while (q--) solve();

}

• Subtask 1: 6 / 6
• Subtask 2: 9 / 9
• Subtask 3: 13 / 13
• Subtask 4: 0 / 32
• Subtask 5: 0 / 29
• Subtask 6: 0 / 11