Submission #1029842

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1029842	2024-07-21T12:03:22 Z	Unforgettablepl	Tourism (JOI23_tourism)	C++17	7 / 100	79 ms	14264 KB

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.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	2 ms	4444 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	2 ms	4444 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	4444 KB	Output is correct
2	Correct	2 ms	4348 KB	Output is correct
3	Correct	4 ms	4700 KB	Output is correct
4	Correct	51 ms	10616 KB	Output is correct
5	Correct	47 ms	11608 KB	Output is correct
6	Correct	64 ms	12568 KB	Output is correct
7	Correct	69 ms	14164 KB	Output is correct
8	Correct	68 ms	14092 KB	Output is correct
9	Correct	76 ms	14264 KB	Output is correct
10	Correct	74 ms	14144 KB	Output is correct
11	Correct	79 ms	14224 KB	Output is correct
12	Correct	68 ms	13976 KB	Output is correct
13	Correct	70 ms	13908 KB	Output is correct
14	Correct	62 ms	13968 KB	Output is correct
15	Correct	29 ms	11796 KB	Output is correct
16	Correct	48 ms	13916 KB	Output is correct
17	Correct	50 ms	6740 KB	Output is correct