Submission #1029842

#	Time	Username	Problem	Language	Result	Execution time	Memory
1029842		Unforgettablepl	Tourism (JOI23_tourism)	C++17	7 / 100	79 ms	14264 KiB

tourism

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int INF = 1e18;

struct segtree{
	vector<int> tree;
	segtree():tree(262144){}
	void update(int k,int x){
		k+=131072;
		tree[k]=x;
		while(k/=2){
			tree[k]=min(tree[2*k],tree[2*k+1]);
		}
	}
	int get(int a,int b){
		a+=131072;b+=131072;
		int ans = INF;
		while(a<=b){
			if(a&1)ans=min(ans,tree[a++]);
			if(b%2 == 0)ans=min(ans,tree[b--]);
			a/=2;b/=2;
		}
		return ans;
	}
};

int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,m,q;
	cin >> n >> m >> q;
	vector<vector<int>> adj(n+1);
	for(int i=1;i<n;i++){
		int a,b;cin>>a>>b;
		adj[a].emplace_back(b);
		adj[b].emplace_back(a);
	}
	vector<int> checkpoints(m+1);
	segtree maxi;
	segtree mini;
	for(int i=1;i<=m;i++){
		int x;cin>>x;
		mini.update(i,x);
		maxi.update(i,-x);
	}
	for(int i=1;i<=q;i++){
		int l,r;
		cin >> l >> r;
		cout << -maxi.get(l,r)-mini.get(l,r)+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