이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using ll = long long;
using pii = pair<int, int>;
#define sz(x) int(x.size())
ll* c;
vi* children;
vi lst;
vector<pii> queries[400'001];
int* res;
void dfs(int u)
{
cerr << "dfs " << u << '\n';
for(pii qr : queries[u])
{
cerr << "qr " << qr.first << ' ' << qr.second << '\n';
int bt = sz(lst);
for(int e = 19; e >= 0; e--)
{
if(bt - (1<<e) >= 0 && lst[bt - (1<<e)] <= qr.second)
bt -= (1<<e);
}
res[qr.first] = sz(lst) - bt;
}
lst.push_back(u);
for(int v : children[u])
{
cerr << "child " << v << '\n';
dfs(v);
}
lst.pop_back();
}
int main()
{
int N;
cin >> N;
ll d[N+1];
c = d;
c[0] = 0;
for(int i = 1; i <= N; i++)
{
cin >> c[i];
c[i] += c[i-1];
}
int lst[N+1];
for(int i = 0; i <= N; i++)
lst[i] = i;
sort(lst, lst+N+1, [] (int u, int v)
{
if(c[u] == c[v])
return u < v;
return c[u] < c[v];
});
int nxt[N+1];
for(int i = 0; i <= N; i++)
nxt[i] = N+1;
for(int i = 0; i+1 <= N; i++)
{
if(c[lst[i]] == c[lst[i+1]])
nxt[lst[i]] = lst[i+1];
}
for(int i = 0; i <= N; i++)
cerr << nxt[i] << ' ';
cerr << '\n';
for(int i = N-1; i >= 0; i--)
nxt[i] = min(nxt[i], nxt[i+1]);
for(int i = 0; i <= N; i++)
cerr << nxt[i] << ' ';
cerr << '\n';
int Q;
cin >> Q;
cerr << "done\n";
// vector<pii> qrs[1+N];
// queries = qrs;
for(int j = 1; j <= Q; j++)
{
int L, R;
cin >> L >> R;
L--;
queries[L].push_back({j, R});
}
vi chld[2+N];
children = chld;
for(int i = 0; i <= N; i++)
children[nxt[i]].push_back(i);
int rs[1+Q];
res = rs;
dfs(N+1);
for(int j = 1; j <= Q; j++)
cout << res[j] << '\n';
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |