Submission #836042

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
836042	2023-08-24T06:15:25 Z	veehj	Tourism (JOI23_tourism)	C++17	7 / 100	293 ms	10808 KB

tourism

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

typedef long long ll;
typedef long double ld;
#define F first
// #define S second
#define pb push_back
#define sz(a) (int)a.size()
#define all(x) (x).begin(), (x).end()

typedef ll S;

S op(S a, S b){ return min(a, b); }
S op2(S a, S b){ return max(a, b); }
S e(){ return 1e7; }
S e2(){ return 0; }

struct segtree{
  S n;
  vector<S> d;
  vector<S> d2;
  segtree(vector<S>& a){
    n=a.size();
    d.assign(4*n, e());
    d2.assign(4*n, e2());
    build(a);
  }
  void build(vector<S>& a, ll nw=1, ll l=0, ll r=-1){
    if(r==-1) r=n-1;
    if(r==l){
      d[nw]=a[l];
      d2[nw]=a[l];
      return;
    }
    build(a, 2*nw, l, (l+r)/2);
    build(a, 2*nw+1, (l+r)/2+1, r);
    d[nw]=op(d[2*nw], d[2*nw+1]);
    d2[nw]=op2(d2[2*nw], d2[2*nw+1]);
  }
  S find(ll fl, ll fr, ll nw=1, ll l=0, ll r=-1){
    if(r==-1) r=n-1;
    if(fr<fl) return e();
    if(fl<=l && r<=fr) return d[nw];
    ll md=(l+r)/2;
    return op(find(fl, min(md, fr), nw*2, l, md), find(max(md+1, fl), fr, nw*2+1, md+1, r));
  }
  S find2(ll fl, ll fr, ll nw=1, ll l=0, ll r=-1){
    if(r==-1) r=n-1;
    if(fr<fl) return e2();
    if(fl<=l && r<=fr) return d2[nw];
    ll md=(l+r)/2;
    return op2(find2(fl, min(md, fr), nw*2, l, md), find2(max(md+1, fl), fr, nw*2+1, md+1, r));
  }
};

int main() {
  int n, m, q; cin >> n >> m >> q;
  int a, b; for(int i=0; i<n-1; i++) cin >> a >> b;
  vector<ll> v(m); for(auto& u : v) cin >> u;
  segtree seg(v);
  while(q--){
    cin >> a >> b;
    cout << seg.find2(a-1, b-1)-seg.find(a-1, b-1)+1 << endl;
  }
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	212 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	1 ms	300 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	5 ms	340 KB	Output is correct
4	Correct	206 ms	8908 KB	Output is correct
5	Correct	184 ms	6592 KB	Output is correct
6	Correct	173 ms	8568 KB	Output is correct
7	Correct	291 ms	10708 KB	Output is correct
8	Correct	286 ms	10808 KB	Output is correct
9	Correct	284 ms	10768 KB	Output is correct
10	Correct	293 ms	10788 KB	Output is correct
11	Correct	287 ms	10808 KB	Output is correct
12	Correct	264 ms	10572 KB	Output is correct
13	Correct	257 ms	10528 KB	Output is correct
14	Correct	272 ms	10564 KB	Output is correct
15	Correct	167 ms	2020 KB	Output is correct
16	Correct	248 ms	10408 KB	Output is correct
17	Correct	230 ms	8780 KB	Output is correct