Submission #837204

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
837204	2023-08-25T08:04:16 Z	veehz	Tourism (JOI23_tourism)	C++17	7 / 100	249 ms	7680 KB

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.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	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	5 ms	340 KB	Output is correct
4	Correct	177 ms	4724 KB	Output is correct
5	Correct	162 ms	4820 KB	Output is correct
6	Correct	151 ms	5908 KB	Output is correct
7	Correct	240 ms	7612 KB	Output is correct
8	Correct	238 ms	7680 KB	Output is correct
9	Correct	249 ms	7640 KB	Output is correct
10	Correct	241 ms	7620 KB	Output is correct
11	Correct	247 ms	7668 KB	Output is correct
12	Correct	232 ms	7440 KB	Output is correct
13	Correct	225 ms	7444 KB	Output is correct
14	Correct	229 ms	7404 KB	Output is correct
15	Correct	167 ms	2000 KB	Output is correct
16	Correct	218 ms	7288 KB	Output is correct
17	Correct	211 ms	5660 KB	Output is correct