# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
891560 | fanwen | Sum Zero (RMI20_sumzero) | C++17 | 6 ms | 31320 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define ll long long
#define file(name) \
if(fopen(name".inp", "r")) \
freopen(name".inp", "r", stdin), freopen(name".out", "w", stdout);
const int MAX = 4e5 + 5;
int n, a[MAX], q, f[19][MAX];
map <long long, int> dd;
void you_make_it(void) {
}
signed main() {
#ifdef LOCAL
freopen("TASK.inp", "r", stdin);
freopen("TASK.out", "w", stdout);
#endif
file("sum0");
auto start_time = chrono::steady_clock::now();
cin.tie(0), cout.tie(0) -> sync_with_stdio(0);
long long pref = 0;
cin >> n;
memset(f, -1, sizeof f);
dd[0] = 0;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
pref += a[i];
if(dd.count(pref)) f[0][i] = dd[pref];
f[0][i] = max(f[0][i - 1], f[0][i]);
dd[pref] = i;
// cout << f[0][i] << " \n"[i == n];
}
for (int i = 1; i < 19; ++i) {
for (int u = 1; u <= n; ++u) f[i][u] = (f[i - 1][u] == -1 ? -1 : f[i - 1][f[i - 1][u]]);
}
cin >> q; while(q--) {
int l, r; cin >> l >> r;
int ans = 0;
for (int i = 19 - 1; i >= 0; --i) if(r >= l - 1 && f[i][r] >= l - 1) {
ans |= (1 << i);
r = f[i][r];
}
cout << ans << '\n';
}
auto end_time = chrono::steady_clock::now();
cerr << "\nExecution time : " << chrono::duration_cast <chrono::milliseconds> (end_time - start_time).count() << "[ms]" << endl;
return (0 ^ 0);
}
// Dream it. Wish it. Do it.
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |