Submission #836042

#	Time	Username	Problem	Language	Result	Execution time	Memory
836042		veehj	Tourism (JOI23_tourism)	C++17	7 / 100	293 ms	10808 KiB

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
• Subtask 2: 0 / 5
• Subtask 3: 7 / 7
• Subtask 4: 0 / 18
• Subtask 5: 0 / 24
• Subtask 6: 0 / 41