# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
413664 | blue | Sum Zero (RMI20_sumzero) | C++17 | 1077 ms | 55200 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <vector>
#include <map>
#include <set>
using namespace std;
struct loc
{
long long sm;
int i;
};
bool operator < (loc A, loc B)
{
if(A.sm == B.sm) return A.i < B.i;
return A.sm < B.sm;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N;
cin >> N;
vector<int> nxt[N+2];
multiset<loc> L;
long long c[N+2];
c[0] = 0;
L.insert(loc{0, 0});
for(int i = 1; i <= N; i++)
{
cin >> c[i];
c[i] += c[i-1];
L.insert(loc{c[i], i});
}
while(!L.empty())
{
vector<int> p;
long long s = L.begin()->sm;
while(!L.empty() && L.begin()->sm == s)
{
p.push_back(L.begin()->i);
L.erase(L.begin());
}
for(int i = 0; i+1 < p.size(); i++)
{
nxt[ p[i] + 1 ].push_back(p[i+1]);
}
}
// cerr << "check\n";
for(int i = N; i >= 1; i--)
{
if(nxt[i+1].size() == 0) continue;
if(nxt[i].empty())
{
nxt[i].push_back(nxt[i+1][0]);
}
else
{
nxt[i][0] = min(nxt[i][0], nxt[i+1][0]);
}
}
// cerr << "c\n";
for(int j = 1; j <= 20; j++)
{
// cerr << j << '\n';
for(int i = 1; i <= N; i++)
{
if(nxt[i].size() <= j-1) continue;
if(nxt[i][j-1] + 1 > N) continue;
if(nxt[ nxt[i][j-1] + 1 ].size() <= j-1) continue;
nxt[i].push_back(nxt[ nxt[i][j-1] + 1 ][j-1]);
}
}
// cerr << "chec2\n";
int Q;
cin >> Q;
for(int q = 1; q <= Q; q++)
{
int L, R;
cin >> L >> R;
int res = 0;
for(int j = 20; j >= 0; j--)
{
if(j >= nxt[L].size()) continue;
if(nxt[L][j] > R) continue;
L = nxt[L][j] + 1;
// cerr << (1 << j) << ' ' << L << '\n';
res += (1 << j);
}
cout << res << '\n';
}
}
Compilation message (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... |