Submission #1052553

#	Time	Username	Problem	Language	Result	Execution time	Memory
1052553		beaconmc	Fish 3 (JOI24_fish3)	C++14	0 / 100	1138 ms	81320 KiB

Main

#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);
	}
	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> order;
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;
	FOR(i,0,q){
		ll temp1,temp2;
		cin >> temp1 >> temp2;
		temp1--;temp2--;
		order[{temp1, temp2}] = i;
		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) >= cur) hi = mid;
				else lo = mid+1;
			}

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


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

• Subtask 1: 0 / 9
• Subtask 2: 0 / 7
• Subtask 3: 0 / 28
• Subtask 4: 0 / 20
• Subtask 5: 0 / 36