이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
int v[400005], st[400005];
int dp[400005];
typedef long long ll;
int main()
{
int n, q;
cin>>n;
ll mv = 0;
map<ll, int> mp;
vector<pair<int, int>> intv;
for(int i = 1; i <= n; i++)
{
cin>>v[i];
st[i] = mp[-(v[i] + mv)];
if(v[i] == 0)
st[i] = i;
if(st[i] != 0)
intv.push_back({st[i], i});
st[i] = -1;
mv += v[i];
mp[(ll)v[i] - mv] = max(mp[(ll)v[i] - mv], i);
}
if(intv.empty())
{
cin>>q;
for(int i = 1; i <= q; i++)
{
int a;
cin>>a>>a;
cout<<0<<'\n';
}
return 0;
}
int maxst = intv.front().first;
st[intv.front().second] = maxst;
for(int i = 1; i < intv.size(); i++)
{
if(intv[i].first > maxst)
st[intv[i].second] = intv[i].first;
maxst = max(maxst, intv[i].first);
}
intv.clear();
for(int i = 1; i <= n; i++)
{
dp[i] = dp[i - 1];
if(st[i] != -1)
{
intv.push_back({st[i], i});
dp[i] = max(dp[i], 1 + dp[st[i] - 1]);
}
}
cin>>q;
for(int i = 1; i <= q; i++)
{
int a, b;
cin>>a>>b;
int l = 0, r = (int)intv.size() - 1, mij, poz = -1;
while(l < r)
{
mij = (l + r) / 2;
if(a - 1 < intv[mij].first)
r = mij - 1;
else if(a - 1 > intv[mij].second)
l = mij + 1;
else
poz = mij, l = mij + 1;
}
if(poz == -1)
cout<<dp[b]<<'\n';
else if(intv[poz].second > b)
cout<<0<<'\n';
else
cout<<dp[b] - dp[intv[poz].second]<<'\n';
}
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
sumzero.cpp: In function 'int main()':
sumzero.cpp:43:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
43 | for(int i = 1; i < intv.size(); i++)
| ~~^~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |