oj.uz

Submission #491451

# Submission time Handle Problem Language Result Execution time Memory
491451 2021-12-02T11:53:11 Z beepbeepsheep Pilot (NOI19_pilot) C++17
0 / 100
 125 ms 262148 KB 
#include <bits/stdc++.h>

using namespace std;
#define ll int
#define endl '\n'
typedef pair<ll,ll> ii;
//const ll inf=1e15;
const ll mod=1e9+7;
const ll maxn=1e6+5;

ll parent[maxn];
ll ran[maxn];
ll sz[maxn];
stack<ll> cnt[maxn];
ll ans[maxn];
bool vis[maxn];
ll root(ll x){
    if (parent[x]==x) return x;
    return parent[x]=root(parent[x]);
}
void connect(ll a,ll b){
    ll root_a=a,root_b=b;
    if (root_a==root_b) return;
    if (ran[root_a]>ran[root_b]){
        sz[root_a]+=sz[root_b];
        parent[root_b]=root_a;
    } else if (ran[root_b]>ran[root_a]){
        sz[root_b]+=sz[root_a];
        parent[root_a]=root_b;
    } else{
        sz[root_a]+=sz[root_b];
        parent[root_b]=root_a;
        ran[root_a]++;
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    for (int i=0;i<maxn;i++){
        parent[i]=i;
    }
    fill(sz,sz+maxn,1);
    ll n,q,ele;
    cin>>n>>q;
    for (int i=0;i<n;i++){
        cin>>ele;
        cnt[ele].push(i+1);
    }
    for (int i=1;i<maxn;i++){
        ans[i]=ans[i-1];
        while (!cnt[i].empty()){
            ll a=cnt[i].top();
            cnt[i].pop();
            vis[a]=1;
            ll root_l=root(a-1);
            ll root_r=root(a+1);
            if (vis[a-1] && vis[a+1]){
                ans[i]+=sz[root_l]*sz[root_r]+(sz[root_l]+sz[root_r]+1);
                connect(root_l,a);
                connect(root_r,a);
            } else if (vis[a-1]){
                ans[i]+=sz[root_l]+1;
                connect(a,root_l);
            } else if (vis[a+1]){
                ans[i]+=sz[root_r]+1;
                connect(a,root_r);
            } else{
                ans[i]+=1;
            }
        }
    }
    for (int i=0;i<q;i++){
        cin>>ele;
        cout<<ans[ele]<<endl;
    }
    return 0;
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 115 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 115 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 115 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 115 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 119 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 125 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 117 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 115 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #9
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 115 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #10
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 115 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -