oj.uz

Submission #1052573

# Submission time Handle Problem Language Result Execution time Memory
1052573 2024-08-10T16:37:31 Z beaconmc Fish 3 (JOI24_fish3) C++14
28 / 100
 1540 ms 108660 KB 
#include <bits/stdc++.h>
 
typedef long long ll;
#define FOR(i,x,y) for(ll i=x; i<y; i++)
#define FORNEG(i,x,y) for(ll i=x; i>y; i--)

using namespace std;

const ll maxn = 300005;
ll tree[maxn*4];
ll lazy[maxn*4];


ll calc(ll k, ll x, ll y){
	if (lazy[k] == -1) return tree[k];
	else return lazy[k] * (y-x+1);
}
void push(ll k, ll x, ll y){
	if (lazy[k] != -1){
		lazy[k*2] = lazy[k];
		lazy[k*2+1] = lazy[k];
		tree[k] = lazy[k] * (y-x+1);
		lazy[k] = -1;
	}
}
void update(ll a, ll b, ll val, ll k=1, ll x=0, ll y = maxn-1){
	if (a>y || b<x) return;
	if (a<=x && y<=b){
		lazy[k] = val;
		return;
	}
	push(k,x,y);
	ll mid = (x+y)/2;
	update(a,b,val,k*2,x,mid);
	update(a,b,val,k*2+1,mid+1,y);

	tree[k] = calc(k*2,x,mid) + calc(k*2+1, mid+1, y);
}

ll query(ll a, ll b, ll k=1, ll x = 0, ll y = maxn-1){
	if (a>y || b<x) return 0;
	if (a<=x && y<=b){
		return calc(k,x,y);
	}
	push(k,x,y);
	ll mid = (x+y)/2;
	return query(a,b,k*2,x,mid) + query(a,b,k*2+1,mid+1,y);
}

map<vector<ll>, ll> vals;
int main(){
	FOR(i,0,maxn*4) tree[i] = 0, lazy[i] = -1;
	ll n,d;
	cin >> n >> d;
	vector<ll> arr(n);
	FOR(i,0,n) cin >> arr[i];
	vector<ll> pref(n);
	pref[0] = arr[0];
	FOR(i,1,n) pref[i] = pref[i-1] + arr[i];
	ll q;
	cin >> q;
	vector<vector<ll>> queries;
	vector<vector<ll>> origqueries;
	FOR(i,0,q){
		ll temp1,temp2;
		cin >> temp1 >> temp2;
		temp1--;temp2--;

		origqueries.push_back({temp1, temp2});
		queries.push_back({temp2, temp1});
	}

	sort(queries.begin(), queries.end());
	for (auto&i : queries) swap(i[0], i[1]);


	ll cur = 0;


	vector<ll> ans(q);

	FOR(i,0,n){
		update(i,i,arr[i]);
	}

	
	for (auto&i : queries){

		while (cur <= i[1]){

			ll lo = 0;
			ll hi = cur;
			while (lo < hi){
				ll mid = (lo+hi)/2;
				if (query(mid, mid) >= arr[cur]) hi = mid;
				else lo = mid+1;
			}


			update(lo, cur, arr[cur]);
			cur++;
		}



		vals[i] = (pref[i[1]]-pref[i[0]] + arr[i[0]]) - query(i[0], i[1]);
	}
	for (auto&i : origqueries) cout << vals[i] << "\n";
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 19032 KB Output is correct
2 Correct 2 ms 19036 KB Output is correct
3 Incorrect 2 ms 19036 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1440 ms 94832 KB Output is correct
2 Correct 1498 ms 99924 KB Output is correct
3 Incorrect 622 ms 92588 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 577 ms 93212 KB Output is correct
2 Correct 1540 ms 107020 KB Output is correct
3 Correct 1481 ms 108184 KB Output is correct
4 Correct 1380 ms 105360 KB Output is correct
5 Correct 1381 ms 108660 KB Output is correct
6 Correct 1312 ms 100772 KB Output is correct
7 Correct 1342 ms 100696 KB Output is correct
8 Correct 1380 ms 102996 KB Output is correct
9 Correct 1352 ms 105616 KB Output is correct
10 Correct 1391 ms 103648 KB Output is correct
11 Correct 1284 ms 102280 KB Output is correct
12 Correct 1327 ms 106008 KB Output is correct
13 Correct 1340 ms 103528 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1150 ms 93456 KB Output is correct
2 Correct 1181 ms 101268 KB Output is correct
3 Correct 737 ms 96912 KB Output is correct
4 Correct 1290 ms 102496 KB Output is correct
5 Correct 1197 ms 107660 KB Output is correct
6 Correct 1220 ms 106892 KB Output is correct
7 Correct 1104 ms 106108 KB Output is correct
8 Correct 1258 ms 104928 KB Output is correct
9 Incorrect 1225 ms 100412 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 19032 KB Output is correct
2 Correct 2 ms 19036 KB Output is correct
3 Incorrect 2 ms 19036 KB Output isn't correct
4 Halted 0 ms 0 KB -