답안 #836042

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
836042 2023-08-24T06:15:25 Z veehj Tourism (JOI23_tourism) C++17
7 / 100
293 ms 10808 KB
#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;
  }
}
# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 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
# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -