Submission #1214224

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214224		PenguinsAreCute	Tourism (JOI23_tourism)	C++17	7 / 100	170 ms	2900 KiB

tourism

#include <bits/stdc++.h>
using namespace std;
struct seg {
	int n;
	vector<int> v;
	seg(int _n): n(_n), v(2*_n,0) {}
	void up(int x, int u) {
		for(v[x+=n]=u;x>>=1;)
			v[x]=max(v[x<<1],v[x<<1|1]);
	}
	int qry(int l, int r) {
		int ans = -1e9;
		for(l+=n,r+=n+1;l<r;l>>=1,r>>=1) {
			if(l&1)
				ans=max(ans,v[l++]);
			if(r&1)
				ans=max(ans,v[--r]);
		}
		return ans;
	}
};
int main() {
	int n, m, q;
	cin >> n >> m >> q;
	for(int i=0,trash;i<2*n-2;i++)
		cin >> trash;
	int c[m];
	seg minSeg(m), maxSeg(m);
	for(int i=0;i<m;i++) {
		cin>>c[i];
		minSeg.up(i, -c[i]);
		maxSeg.up(i, c[i]);
	}
	for(int i=0,l,r;i<q;i++) {
		cin >> l >> r;
		cout << maxSeg.qry(l-1,r-1) + minSeg.qry(l-1,r-1) + 1 << "\n";
	}
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 5
• Subtask 3: 7 / 7
• Subtask 4: 0 / 18
• Subtask 5: 0 / 24
• Subtask 6: 0 / 41