Submission #1179650

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179650		Nonoze	Fish 3 (JOI24_fish3)	C++20	0 / 100	1059 ms	27880 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define fi first
#define se second
#define cmin(a, b) a=min(a, b)
#define cmax(a, b) a=max(a, b)

void solve();

signed main() {
	ios::sync_with_stdio(0); cin.tie(0);
	solve();
	return 0;
}

int k;
int n, q;
vector<int> a;

void solve() {
	cin >> n >> k;
	a.resize(n); for (auto &u: a) cin >> u;
	vector<int> pref=a; for (int i=1; i<n; i++) pref[i]+=pref[i-1];
	cin >> q;
	vector<vector<int>> queries;
	vector<int> ans(q, -1);
	for (int i=0; i<q; i++) {
		int l, r; cin >> l >> r; l--, r--;
		queries.pb({l, r, i});
		ans[i]=pref[r]-(l?pref[l-1]:0);
	}
	int SQRT=sqrt(n);
	sort(all(queries), [&](auto &x, auto &y){
		if (x[0]/SQRT==y[0]/SQRT) return x[1]<y[1];
		return x[0]/SQRT<y[0]/SQRT;
	});
	deque<int> dq;
	int L=queries[0][0], R=queries[0][0]-1, val=0;
	for (int i=0; i<q; i++) {
		int l=queries[i][0], r=queries[i][1];
		if (i && queries[i-1][0]/SQRT!=l/SQRT) {
			dq.clear();
			L=l, R=l-1, val=0;
		}
		while (R<r) {
			R++;
			while (!dq.empty() && a[dq.back()]>a[R]) {
				int nb=dq.back();
				dq.pop_back();
				if (dq.empty()) val-=a[nb]*(nb-L+1);
				else val-=a[nb]*(nb-dq.back());
			}
			if (dq.empty()) val+=(R-L+1)*a[R];
			else val+=(R-dq.back())*a[R];
			dq.push_back(R);
		}
		while (L>l) {
			L--;
			if (dq.empty() || a[L]<dq.front()) dq.push_front(L), val+=a[L];
			else val+=a[dq.front()];
		}
		while (L<l) {
			if (dq.front()==L) dq.pop_front(), val-=a[L];
			else val-=a[dq.front()];
			L++;
		}
		ans[queries[i][2]]-=val;
	}
	for (auto &u: ans) cout << u << endl;
}

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