80分求助
查看原帖
80分求助
390770
D2T1xubiaoshi楼主2024/1/22 13:43

wa subtask23,,,

//qoj8016
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 2e6 + 10;
priority_queue<ll> q, qq;
int n, m, bit[N], E, a[N], b[N], c[N], d[N];
ll sum[N], k[N];

void read(int &x){
	x = 0;
	char ch = getchar();
	int w = 1;
	while(ch < '0' || ch > '9'){
		if(ch == '-'){
			w = -w;
		}
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9'){
		x = x * 10 + ch - '0';
		ch = getchar();
	}
	x *= w;
}

void add(int x, int v){
	while(x <= m){
		bit[x] += v;
		x += x & -x;
	}	
}
int ask(int x){
	int res = 0;
	while(x){
		res += bit[x];
		x -= x & -x;
	}
	return res;
}

int main(){
	read(n);
	read(E);
	for(int i = 1; i <= n; ++ i){
		read(a[i]);
	}
	for(int i = 1; i <= n; ++ i){
		read(b[i]);
		sum[i] = sum[i-1] + b[i] - a[i];
		c[i] = min(b[i] - a[i], 0);
		d[i] = min(b[i], a[i]);
		k[i] = sum[i];
	}
	sort(k + 1, k + n + 2);
	m = unique(k + 1, k + n + 2) - k - 1;
	for(int i = 0; i <= n; ++ i){
		sum[i] = lower_bound(k + 1, k + m + 1, sum[i]) - k;
	}
	ll ne = E, ans = 0;
	ll mx = -1e18;
	q.push(-1e18);
	for(int l = 1, r = 1; l <= n; ++ l){
		r = max(r, l-1);
		while(r <= n){
			if(ne + c[r] >= max(mx, (ll)d[r])){
				ne += c[r];
				q.push(d[r]);
				add(m-sum[r]+1, 1);
				mx = max(mx, (ll)d[r]);
				++ r;
			} else {
				break;
			}
		}
		ans += ask(m-sum[l-1]+1);
		ne -= c[l];
		qq.push(d[l]);
		add(m-sum[l]+1, -1);
		while(!qq.empty() && !q.empty() && q.top() == qq.top()){
			q.pop();
			qq.pop();
		}
		mx = q.top();
	}
	printf("%lld\n", ans);
	return 0;
}
2024/1/22 13:43
加载中...