Submission #1249080

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249080		nasjes	Pilot (NOI19_pilot)	C++20	100 / 100	386 ms	106772 KiB

pilot

#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <algorithm>
#include <set>
#include <queue>
#include <map>
#include <stack>
#include <bitset>
#include <string>
#include <cstring>
#include <iterator>
#include <random>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef long double ld;
const ll dim = 2*(1e6)+7;
//const ll mod = 1e9 + 7;
const ll inf = 1e17 + 77;
#define endl "\n"
#define fi first
#define pb push_back
#define se second
#define vll vector<ll>

ll n, m, k;
ll a[dim], boss[dim];
vll pos[dim];
ll sz[dim];
ll ans=0;
ll findboss(ll v){
    if(boss[v]==v)return v;
    return boss[v]=findboss(boss[v]);
}
void unite(ll x, ll y){
    ll x1=findboss(x);
    ll y1=findboss(y);
    if(x1==y1)return;
    if(sz[x1]>sz[y1])swap(x1, y1);
    boss[y1]=x1;
    ans-=(sz[x1])*(sz[x1]+1)/2;
    ans-=(sz[y1])*(sz[y1]+1)/2;
    sz[x1]+=sz[y1];
   // cout<<x1<<" "<<y1<<" "<<sz[x1]<<endl;
    ans+=(sz[x1])*(sz[x1]+1)/2;
}
ll qu[dim];
int main() {

    ll  u, w,q,  v, y;
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n>>q;
    ll mx=0;
    for(int i=1; i<=n; i++){
        cin>>a[i];
        mx=max(mx, a[i]);
        pos[a[i]].pb(i);
    }
    for(int i=1; i<=n; i++){
        boss[i]=i;
        sz[i]=0;
    }
    for(int i=1; i<=1e6; i++){
        for(auto x: pos[i]){
            sz[x]=1;
        }
        for(auto x: pos[i]){
            ans++;
            if(a[x-1]<=i && x-1>=1)unite(x-1, x);
            if(a[x+1]<=i && x+1<=n)unite(x+1, x);
           // cout<<ans<<" ";
        }
        qu[i]=ans;
        //cout<<ans<<endl;
    }
    for(int i=1; i<=q; i++){
        cin>>y;
        cout<<qu[y]<<endl;
    }

    return 0;
}

• Subtask 1: 3 / 3
• Subtask 2: 10 / 10
• Subtask 3: 12 / 12
• Subtask 4: 15 / 15
• Subtask 5: 5 / 5
• Subtask 6: 9 / 9
• Subtask 7: 14 / 14
• Subtask 8: 10 / 10
• Subtask 9: 11 / 11
• Subtask 10: 11 / 11