이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
// Esti <3
//\
šťastia pre nás :)
// you're already the best
// _
// ^ ^ //
// >(O_O)<___//
// \ __ __ \
// \\ \\ \\\\
#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize("O3","unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#pragma GCC optimize("O3")
#pragma GCC target("popcnt")
using ll = long long;
//#define int long long
#define forn(i,n) for(int i=0; i<(n); ++i)
#define pb push_back
#define pi pair<int,int>
#define f first
#define s second
#define vii(a,n) vector<int> a(n); forn(i,n) cin>>a[i];
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
//mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
//const ll inf = 1e18;
//const ll mod = 998244353;
// \
\
:smiling_face_with_3_hearts: :smiling_face_with_3_hearts: :smiling_face_with_3_hearts:
//vidime sa veľmi skoro, moje slnko
//[] {}
//кто андрей столетний - того на вилы
const int N=4e5+5;
const int K=600;
int par[N];
int go[N];
int n,q;
int u,i,j;
int l,r;
int ans;
int s=0;
unordered_map<int,int> m;
int a[N];
//i'm not retarded, it's ml retarded
void solve() {
cin>>n;
for(i=0; i<n; ++i) cin>>a[i];
m[0]=n;
for(i=0; i<n+1; ++i) par[i]=n+1;
for(i=n-1; i>=0; --i) {
s+=a[i];
if (m.count(s)) par[i]=m[s];
m[s]=i;
}
m.clear();
u=n+1;
for(i=n-1; i>=0; --i) {
if (par[i]>-1) u=min(u,par[i]);
par[i]=u;
}
for(i=0; i<n; ++i) {
u=i;
for(j=0; j<K && u<=n; ++j) {
u=par[u];
}
go[i]=u;
}
cin>>q;
for(i=0;i<q;++i) {
cin>>l>>r;
u=l-1;
ans=0;
while (go[u] <= r) {
ans+=K;
u=go[u];
}
while (par[u] <= r) {
++ans;
u = par[u];
}
cout<<ans<<'\n';
}
}
int32_t main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int t=1;
//cin>>t;
while (t--) solve();
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
sumzero.cpp:3:1: warning: multi-line comment [-Wcomment]
3 | //\
| ^
sumzero.cpp:9:1: warning: multi-line comment [-Wcomment]
9 | // \ __ __ \
| ^
sumzero.cpp:36:1: warning: multi-line comment [-Wcomment]
36 | // \
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |