제출 #1170140

#제출 시각아이디문제언어결과실행 시간메모리
1170140patgraTwo Antennas (JOI19_antennas)C++20
13 / 100
422 ms189964 KiB
#include <bits/stdc++.h> #define rep(a,b,c) for(auto a = (b); a != (c); a++) #define repD(a,b,c) for(auto a = (b); a != (c); a--) #define repIn(a, b) for(auto& a : (b)) #define repIn2(a, b, c) for(auto& [a, b] : (c)) constexpr bool dbg = 0; #define DEBUG if constexpr(dbg) #define DC DEBUG std::cerr #define eol std::endl #define ll long long #define pb push_back using namespace std; constexpr int maxLog = 12; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int n, q; cin >> n; vector<int> h(n), a(n), b(n); rep(i, 0, n) cin >> h[i] >> a[i] >> b[i]; if(n <= 2000) { int st[n][n][maxLog]; repIn(i, st) repIn(ii, i) repIn(iii, ii) iii = -1; rep(i, 0, n - 1) rep(j, i + 1, n) { if(a[i] + i > j || b[i] + i < j) continue; if(j - a[j] < i || j - b[j] > i) continue; st[i][j][0] = st[j][i][0] = abs(h[i] - h[j]); DC << i << ' ' << j << ' ' << st[i][j][0] << eol;; } rep(k, 1, maxLog) rep(i, 0, n) rep(j, 0, n) { int i1 = min(n - 1, i + (1 << (k - 1))); int j1 = min(n - 1, j + (1 << (k - 1))); st[i][j][k] = max(max(st[i][j][k - 1], st[i][j1][k - 1]), max(st[i1][j][k - 1], st[i1][j1][k - 1])); } int l, r; cin >> q; rep(i, 0, q) { cin >> l >> r; l--; r--; int k = 31 - __builtin_clz(r - l + 1); int r1 = r - (1 << k) + 1; int ans =max(max(st[l][l][k], st[l][r1][k]), max(st[r1][l][k], st[r1][r1][k])); cout << ans << '\n'; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...