oj.uz

답안 #928966

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
928966 2024-02-17T10:20:35 Z winter0101 Sum Zero (RMI20_sumzero) C++
100 / 100
 243 ms 16868 KB 
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long ,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
#define pil pair<int,long long>
const int maxn=4e5+10;
int nxt[maxn],bit[maxn],in[maxn],out[maxn];
int n,tme=0;
void dfs(int u){
in[u]=++tme;
if (u==0){
for2(v,n+1,n){
int l=1,r=min(v,n),as=-1;
while (l<=r){
int mid=(l+r)/2;
if (nxt[mid]==v){
as=mid;
l=mid+1;
}
else if (nxt[mid]>v){
r=mid-1;
}
else l=mid+1;
}
if (as!=-1)dfs(as);
}
}
else {
int v=u;
while (v){
if (nxt[v]!=nxt[u])break;
int l=1,r=v,as=-1;
while (l<=r){
int mid=(l+r)/2;
if (nxt[mid]+1==v){
as=mid;
l=mid+1;
}
else if (nxt[mid]+1>v){
r=mid-1;
}
else l=mid+1;
}
if (as!=-1)dfs(as);
v--;
}
}
out[u]=tme;
}
void add(int pos,int val){
for(;pos<=n;pos+=(pos-(pos&(pos-1))))bit[pos]+=val;
}
void add(int l,int r,int val){
add(l,val);
add(r+1,-val);
}
int get(int pos){
int sum=0;
for(;pos>=1;pos-=(pos-(pos&(pos-1))))sum+=bit[pos];
return sum;
}
int lep[maxn],rai[maxn],id[maxn];
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("temp.INP","r",stdin);
    //freopen("temp.OUT","w",stdout);
    cin>>n;
    vector<pli>a(n+1);
    for1(i,1,n){
    cin>>a[i].fi;
    a[i].fi+=a[i-1].fi;
    a[i].se=i;
    }
    a[0].fi=a[0].se=0;
    sort(all(a));
    for1(i,0,n){
    nxt[a[i].se+1]=n+1;
    if (i<n&&a[i].fi==a[i+1].fi){
    nxt[a[i].se+1]=a[i+1].se;
    }
    }
    vector<pli>().swap(a);
    for2(i,n-1,1)nxt[i]=min(nxt[i],nxt[i+1]);
    auto f=[&](int u){
    int l=u,r=n,ans=u;
    while (l<=r){
    int mid=(l+r)/2;
    if (nxt[mid]==nxt[u]){
    l=mid+1;
    ans=mid;
    }
    else r=mid-1;
    }
    return ans;
    };
    dfs(0);
    int q;
    cin>>q;
    for1(i,1,q)cin>>lep[i]>>rai[i],id[i]=i,lep[i]=f(lep[i]);
    sort(id+1,id+1+q,[](int i,int j){
    return rai[i]<rai[j];
    });
    int p=1,qr=1;
    for1(i,1,n){
    while (nxt[p]<i&&p<i){
    p++;
    }
    if (nxt[p]==i){
    for1(j,p,i){
    if (nxt[j]>i)break;
    p=j;
    if (j<i&&nxt[j]==nxt[j+1])continue;
    add(in[j],out[j],1);
    }
    }
    while (qr<=q){
    if (rai[id[qr]]!=i)break;
    lep[id[qr]]=get(in[lep[id[qr]]]);
    qr++;
    }
    }
    for1(i,1,q)cout<<lep[i]<<'\n';
}

Subtask #1
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 10840 KB Output is correct
2 Correct 3 ms 10844 KB Output is correct
3 Correct 3 ms 10844 KB Output is correct
4 Correct 3 ms 10840 KB Output is correct
5 Correct 3 ms 10844 KB Output is correct
6 Correct 3 ms 10844 KB Output is correct

Subtask #2
39.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 10840 KB Output is correct
2 Correct 3 ms 10844 KB Output is correct
3 Correct 3 ms 10844 KB Output is correct
4 Correct 3 ms 10840 KB Output is correct
5 Correct 3 ms 10844 KB Output is correct
6 Correct 3 ms 10844 KB Output is correct
7 Correct 48 ms 12072 KB Output is correct
8 Correct 55 ms 11300 KB Output is correct
9 Correct 51 ms 11736 KB Output is correct
10 Correct 48 ms 12020 KB Output is correct
11 Correct 50 ms 11308 KB Output is correct
12 Correct 52 ms 11828 KB Output is correct

Subtask #3
39.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 10840 KB Output is correct
2 Correct 3 ms 10844 KB Output is correct
3 Correct 3 ms 10844 KB Output is correct
4 Correct 3 ms 10840 KB Output is correct
5 Correct 3 ms 10844 KB Output is correct
6 Correct 3 ms 10844 KB Output is correct
7 Correct 48 ms 12072 KB Output is correct
8 Correct 55 ms 11300 KB Output is correct
9 Correct 51 ms 11736 KB Output is correct
10 Correct 48 ms 12020 KB Output is correct
11 Correct 50 ms 11308 KB Output is correct
12 Correct 52 ms 11828 KB Output is correct
13 Correct 205 ms 16868 KB Output is correct
14 Correct 198 ms 13928 KB Output is correct
15 Correct 219 ms 15872 KB Output is correct
16 Correct 216 ms 16052 KB Output is correct
17 Correct 201 ms 14040 KB Output is correct
18 Correct 243 ms 15832 KB Output is correct