이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const int MAXN = 4e5 + 10;
const int MAXQ = 4e5 + 10;
const int MAXLOG = 22;
int n, q;
int a[MAXN];
int nxt[MAXN];
int lift[MAXN][MAXLOG];
pair < int, int > queries[MAXQ];
ll ans[MAXN];
map < ll, int > sums;
void read()
{
cin >> n;
for(int i = 1; i <= n; i++)
{
cin >> a[i];
}
cin >> q;
for(int i = 1; i <= q; i++)
{
cin >> queries[i].first >> queries[i].second;
}
}
void fill_nxt()
{
int minpos = MAXN - 1;
ll cursum = 0;
for(int i = n + 1; i >= 1; i--)
{
cursum += a[i];
if(sums.find(cursum) != sums.end())
minpos = min(minpos, sums[cursum]);
sums[cursum] = i;
nxt[i] = minpos;
}
}
void solve()
{
for(int i = 1; i <= n + 1; i++)
{
lift[i][0] = nxt[i];
}
lift[MAXN - 1][0] = MAXN - 1;
for(int j = 1; j < MAXLOG; j++)
{
for(int i = 1; i <= n + 1; i++)
{
lift[i][j] = lift[lift[i][j - 1]][j - 1];
}
lift[MAXN - 1][j] = lift[lift[MAXN - 1][j - 1]][j - 1];
}
for(int j = MAXLOG - 1; j >= 0; j--)
{
for(int i = 1; i <= q; i++)
{
int left = queries[i].first;
int right = queries[i].second;
if(lift[left][j] <= right)
{
ans[i] += (1 << j);
left = lift[left][j];
}
queries[i].first = left;
}
}
}
void print()
{
for(int i = 1; i <= q; i++)
{
cout << ans[i] << endl;
}
cout << endl;
}
int main()
{
ios_base :: sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
read();
fill_nxt();
solve();
print();
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |