Submission #837204

#	Time	Username	Problem	Language	Result	Execution time	Memory
837204		veehz	Tourism (JOI23_tourism)	C++17	7 / 100	249 ms	7680 KiB

tourism

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

typedef long long ll;
typedef long double ld;
#define pb push_back

template <typename S, S (*op)(S, S), S (*e)(void)>
struct segtree {
  int _n;
  vector<S> d;
  segtree() : segtree(0) {}
  segtree(int n) : segtree(vector<S>(n, e())) {}
  segtree(vector<S> a) : _n(int(a.size())), d(4 * _n, e()) { build(a); }

  void build(vector<S>& a, int v = 1, int tl = 0, int tr = -1) {
    if (tr == -1) tr = _n;
    if (tl == tr) {
      d[v] = a[tl];
    } else {
      int tm = (tl + tr) / 2;
      build(a, v * 2, tl, tm);
      build(a, v * 2 + 1, tm + 1, tr);
      d[v] = op(d[v * 2], d[v * 2 + 1]);
    }
  }

  void set(int pos, S new_val, int v = 1, int tl = 0, int tr = -1) {
    if (tr == -1) tr = _n;
    if (tl == tr) {
      d[v] = new_val;
    } else {
      int tm = (tl + tr) / 2;
      if (pos <= tm) {
        set(pos, new_val, v * 2, tl, tm);
      } else {
        set(pos, new_val, v * 2 + 1, tm + 1, tr);
      }
      d[v] = op(d[v * 2], d[v * 2 + 1]);
    }
  }

  S prod(int l, int r, int v = 1, int tl = 0, int tr = -1) {
    if (tr == -1) tr = _n;
    if (l > r) return e();
    if (l == tl && r == tr) return d[v];
    int tm = (tl + tr) / 2;
    return op(prod(l, min(r, tm), v * 2, tl, tm),
              prod(max(l, tm + 1), r, v * 2 + 1, tm + 1, tr));
  }
};

struct S {
  int min, max;
};

S op(S a, S b) {
  return {min(a.min, b.min), max(a.max, b.max)};
}

S e() {
  return {INT_MAX, INT_MIN};
}

int main() {
    int n,m,q; cin >> n >> m >> q;
    for(int i=0;i<n-1;i++){
        int k; cin >> k >> k;
    }
    vector<S> a(m);
    for(int i=0;i<m;i++){
        int k; cin >> k;
        a[i] = {k,k};
    }
    segtree<S,op,e> st(a);
    for(int i=0;i<q;i++){
        int l,r; cin >> l >> r;
        l--; r--;
        S s = st.prod(l,r);
        cout << s.max - s.min + 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