oj.uz

Submission #981130

# Submission time Handle Problem Language Result Execution time Memory
981130 2024-05-12T21:29:01 Z aymanrs Fish 3 (JOI24_fish3) C++14
28 / 100
 228 ms 56296 KB 
#include<bits/stdc++.h>
using namespace std;
struct que{
	int l, r, id;
};
void f(int l, int r, list<que>& v, long long a[], long long ans[], long long c[]){
	if(l==r){
		for(auto& i : v){
			if(c[l] >= 0) ans[i.id] = 0;
			else ans[i.id]=-1;
		}
		return;
	}
	int m = l+r>>1;
	list<que> L, R, M;
	for(const que& i : v){
		if(i.r <= m) L.push_back(i);
		else if(i.l > m) R.push_back(i);
		else M.push_back(i);
	}
	v.clear();
	f(l, m, L, a, ans, c);
	f(m+1, r, R, a, ans, c);
	long long S = 0;
	vector<pair<long long, int>> p;
	stack<pair<long long, int>> s;
	long long fs[r-m], Fs[r-m];
	for(int i = m+1;i <= r;i++){
		if(i==m+1) Fs[i-m-1]=0;
		else Fs[i-m-1] = Fs[i-m-2]; 
		if(a[i] <= 0) {
			S -= i*a[i];
			long long k = -a[i];
			while(!s.empty() && k){
				if(k >= s.top().first) {
					k -= s.top().first;
					S -= s.top().first*s.top().second;
					s.pop();
				}
				else {
					S -= k*s.top().second;
					s.top().first -= k;
					k = 0;
					break;
				}
			}
			Fs[i-m-1] += k;
		} else s.push({a[i], i});
		fs[i-m-1] = S;
	}
	S = 0;long long g = 0;
	int pt = m;
	vector<array<long long, 3>> bs = {{0, 0, -1}};
	for(auto& q : M){
		while(pt > q.l){
			if(a[pt] <= 0){
				g -= a[pt];
				S -= a[pt]*pt;
			} else {
				long long k = a[pt];
				if(g >= k){
					g -= k;
					S -= k*pt;
					pt--;
					continue;
				}
				S -= g*pt;
				k -= g;
				g = 0;
				bs.back()[2] = pt;
				bs.push_back({bs.back()[0]+k, bs.back()[1]-k*pt, -1});
			}
			pt--;
		}
		long long k = c[pt];
		if(g > k || k+bs.back()[0]-g < Fs[q.r-m-1]){
			ans[q.id] = -1;
			continue;
		}
		if(!Fs[q.r-m-1]){
			ans[q.id] = S-g*pt+fs[q.r-m-1];
			continue;
		}
		bs.back()[2] = pt;
		int low = 0, high = bs.size()-1, best = 0;
		while(low<=high){
			int mid = low+high>>1;
			if(bs[mid][0] >= Fs[q.r-m-1]) {
				high=mid-1;
			} else {
				best = mid;
				low = mid+1;
			}
		}
		ans[q.id] = S-g*pt+fs[q.r-m-1]+bs[best][1]-(Fs[q.r-m-1]-bs[best][0])*bs[best][2];
	}
}
void solve(){
	int n, d;cin >> n >> d;
	long long a[n+1], c[n+1];a[0]=0;
	for(int i = 1;i <= n;i++) {
		cin >> a[i];
		c[i] = a[i];
	}
	for(int i = n;i >= 1;i--) {
		a[i] = a[i]-a[i-1];
		if(a[i] < 0){
			a[i] = -a[i];
			a[i] = (a[i]+d-1)/d;
			a[i] = -a[i];
		} else a[i] /= d;
		if(c[i] < 0){
			c[i] = -c[i];
			c[i] = (c[i]+d-1)/d;
			c[i] = -c[i];
		} else c[i] /= d;
	}
	int q;cin >> q;
	vector<que> qv;
	for(int i = 0;i < q;i++){
		int l, r;cin >> l >> r;
		qv.push_back({l, r, i});
	}
	sort(qv.begin(), qv.end(), [](const auto& a, const auto& b){
		return a.l > b.l;
	});
	long long ans[q];
	list<que> lv(qv.begin(), qv.end());
	f(1, n, lv, a, ans, c);
	for(int i = 0;i < q;i++) cout << ans[i] << '\n';


}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	solve();
}

Compilation message

Main.cpp: In function 'void f(int, int, std::__cxx11::list<que>&, long long int*, long long int*, long long int*)':
Main.cpp:14:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   14 |  int m = l+r>>1;
      |          ~^~
Main.cpp:87:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   87 |    int mid = low+high>>1;
      |              ~~~^~~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 2 ms 824 KB Output is correct
5 Incorrect 1 ms 344 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 48476 KB Output is correct
2 Correct 163 ms 47488 KB Output is correct
3 Correct 101 ms 39760 KB Output is correct
4 Correct 166 ms 48052 KB Output is correct
5 Incorrect 35 ms 7356 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 43276 KB Output is correct
2 Correct 209 ms 56224 KB Output is correct
3 Correct 206 ms 54968 KB Output is correct
4 Correct 207 ms 56296 KB Output is correct
5 Correct 210 ms 55344 KB Output is correct
6 Correct 180 ms 49384 KB Output is correct
7 Correct 186 ms 48304 KB Output is correct
8 Correct 197 ms 52620 KB Output is correct
9 Correct 203 ms 53080 KB Output is correct
10 Correct 228 ms 51256 KB Output is correct
11 Correct 208 ms 49844 KB Output is correct
12 Correct 216 ms 54800 KB Output is correct
13 Correct 222 ms 54452 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 47404 KB Output is correct
2 Correct 169 ms 47864 KB Output is correct
3 Correct 128 ms 43188 KB Output is correct
4 Correct 186 ms 51108 KB Output is correct
5 Correct 183 ms 53956 KB Output is correct
6 Correct 192 ms 54712 KB Output is correct
7 Correct 216 ms 52980 KB Output is correct
8 Correct 198 ms 55684 KB Output is correct
9 Correct 162 ms 48564 KB Output is correct
10 Incorrect 35 ms 7272 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 2 ms 824 KB Output is correct
5 Incorrect 1 ms 344 KB Output isn't correct
6 Halted 0 ms 0 KB -