oj.uz

답안 #942472

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
942472 2024-03-10T17:20:45 Z bachhoangxuan Sum Zero (RMI20_sumzero) C++17
100 / 100
 224 ms 17848 KB 
// Judges with GCC >= 12 only needs Ofast
// #pragma GCC optimize("O3,no-stack-protector,fast-math,unroll-loops,tree-vectorize")
// MLE optimization
// #pragma GCC optimize("conserve-stack")
// Old judges
// #pragma GCC target("sse4.2,popcnt,lzcnt,abm,mmx,fma,bmi,bmi2")
// New judges. Test with assert(__builtin_cpu_supports("avx2"));
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")
// Atcoder
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma")
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
- insert(x),erase(x)
- find_by_order(k): return iterator to the k-th smallest element
- order_of_key(x): the number of elements that are strictly smaller
*/

#include<bits/stdc++.h>
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
uniform_real_distribution<> pp(0.0,1.0);
#define ll long long
#define ld long double
#define pii pair<int,int>
#define piii pair<int,pii>
#define mpp make_pair
#define fi first
#define se second
const ll inf=1e18;
const int mod=998244353;
const int maxn=400005;
const int B=650;
const int maxs=655;
const int maxm=200005;
const int maxq=1000005;
const int maxl=25;
const int maxa=1000000;
const int root=3;
const int base=101;

int rand_int(int l,int r){
    return l+(int)(rng()%(r-l+1));
}

int n,par[maxn],val[maxn],add[maxn];
int lst[maxn];
ll pre[maxn];

int q;
vector<piii> qq;

int findpar(int u){
    if(u!=par[u]){
        int p=par[u];
        par[u]=findpar(par[u]);
        val[u]+=val[p];
        return par[u];
    }
    return u;
}

void unions(int u,int v){
    u=findpar(u);v=findpar(v);
    if(u==v) return;
    val[v]+=add[v]-add[u];
    par[v]=u;
}

void solve(){
    cin >> n;
    for(int i=1;i<=n;i++) par[i]=i;
    for(int i=1;i<=n;i++){
        cin >> pre[i];
        //pre[i]=rand_int(-1e9,1e9);
        pre[i]+=pre[i-1];

    }
    cin >> q;
    for(int i=1;i<=q;i++){
        int l,r;cin >> l >> r;
        /*
        l=rand_int(1,n);
        r=rand_int(1,n);
        if(l>r) swap(l,r);
        */
        qq.push_back(mpp(r,mpp(l,i)));
    }
    sort(qq.begin(),qq.end());
    sort(par+0,par+n+1,[](int x,int y){
        if(pre[x]!=pre[y]) return pre[x]<pre[y];
        else return x<y;
    });
    for(int i=n;i>=0;i--){
        if(!i || pre[par[i]]!=pre[par[i-1]]) lst[par[i]]=0;
        else lst[par[i]]=par[i-1]+1;
    }
    for(int i=1;i<=n;i++) par[i]=i;
    deque<pii> dq;
    for(int i=1,id=0;id<q;id++){
        while(i<=qq[id].fi){
            dq.push_back({i-1,i});
            if(lst[i]){
                int l=lst[i],p=-1;
                while(!dq.empty() && dq.front().fi<l){
                    int u=dq.front().se;dq.pop_front();
                    if(p!=-1) unions(u,p);
                    p=u;
                }
                if(p!=-1){
                    p=findpar(p);
                    dq.push_back({i,p});
                    add[p]++;
                }
            }
            i++;
        }
        int p=findpar(qq[id].se.fi);
        qq[id].fi=val[qq[id].se.fi]+add[p];
    }
    sort(qq.begin(),qq.end(),[](piii x,piii y){
        return x.se.se<y.se.se;
    });
    for(int i=0;i<q;i++) cout << qq[i].fi << '\n';
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    int test=1;//cin >> test;
    while(test--) solve();
}

Subtask #1
22.0 / 22.0

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

Subtask #2
39.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4696 KB Output is correct
2 Correct 3 ms 6748 KB Output is correct
3 Correct 3 ms 6748 KB Output is correct
4 Correct 3 ms 4696 KB Output is correct
5 Correct 3 ms 6748 KB Output is correct
6 Correct 3 ms 6748 KB Output is correct
7 Correct 48 ms 8900 KB Output is correct
8 Correct 47 ms 10408 KB Output is correct
9 Correct 52 ms 10432 KB Output is correct
10 Correct 52 ms 10440 KB Output is correct
11 Correct 55 ms 10436 KB Output is correct
12 Correct 53 ms 10572 KB Output is correct

Subtask #3
39.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4696 KB Output is correct
2 Correct 3 ms 6748 KB Output is correct
3 Correct 3 ms 6748 KB Output is correct
4 Correct 3 ms 4696 KB Output is correct
5 Correct 3 ms 6748 KB Output is correct
6 Correct 3 ms 6748 KB Output is correct
7 Correct 48 ms 8900 KB Output is correct
8 Correct 47 ms 10408 KB Output is correct
9 Correct 52 ms 10432 KB Output is correct
10 Correct 52 ms 10440 KB Output is correct
11 Correct 55 ms 10436 KB Output is correct
12 Correct 53 ms 10572 KB Output is correct
13 Correct 208 ms 17712 KB Output is correct
14 Correct 200 ms 16344 KB Output is correct
15 Correct 224 ms 17584 KB Output is correct
16 Correct 198 ms 17072 KB Output is correct
17 Correct 204 ms 17368 KB Output is correct
18 Correct 224 ms 17848 KB Output is correct