제출 #1144157

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1144157		t9unkubj	Pilot (NOI19_pilot)	C++20	100 / 100	447 ms	73960 KiB

pilot

#ifdef t9unkubj
#include"debug.cpp"
//#include"template_no_debug.h"
#else 
#define dbg(...) 199958
#endif

#undef _GLIBCXX_DEBUG
#pragma GCC optimize("O3")
using namespace std;
#include<bits/stdc++.h>
using ll=long long;
using ull=unsigned long long;
template<class T>using vc=vector<T>;
template<class T>using vvc=vc<vc<T>>;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,j,n) for(ll i=(j);i<(ll)(n);i++)
#define DREP(i,n,m) for(ll i=(n);i>=(m);i--)
#define drep(i,n) for(ll i=((n)-1);i>=0;i--)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
template<class T,class F>
bool chmin(T &x, F y){
    if(x>y){
        x=y;
        return true;
    }
    return false;
}
template<class T, class F>
bool chmax(T &x, F y){
    if(x<y){
        x=y;
        return true;
    }
    return false;
}
double pass_time=0;
struct dsu{
    vc<int>par;
    dsu(int n):par(n,-1){}
    int root(int a){
        if(par[a]<0)return a;
        return par[a]=root(par[a]);
    }
    int merge(int a,int b){
        a=root(a),b=root(b);
        if(a==b)return 0;
        if(-par[a]<-par[b])swap(a,b);
        par[a]+=par[b];
        par[b]=a;
        return 1;
    }
    int sz(int x){
        return -par[root(x)];
    }
};
void solve(){
    int n,q;
    cin>>n>>q;
    vc<int>h(n);
    vc<int>y(q);
    rep(i,n)cin>>h[i];
    rep(i,q)cin>>y[i];
    vc<ll>ans(q);

    dsu dsu(n);
    vc<array<ll,3>>ev;
    rep(i,n){
        ev.push_back({h[i],0,i});
    }
    rep(i,q){
        ev.push_back({y[i],1,i});
    }
    ll now_ans=0;
    sort(all(ev));
    for(auto&[v,t,i]:ev){
        if(t==0){
            if(i&&h[i-1]<=h[i]){
                now_ans-=1ll*dsu.sz(i-1)*(dsu.sz(i-1)+1)/2;
                dsu.merge(i,i-1);
            }
            if(i<n-1&&h[i+1]<h[i]){
                now_ans-=1ll*dsu.sz(i+1)*(dsu.sz(i+1)+1)/2;
                dsu.merge(i,i+1);
            }
            now_ans+=1ll*dsu.sz(i)*(dsu.sz(i)+1)/2;
        }else{
            ans[i]=now_ans;
        }
    }
    rep(i,q)cout<<ans[i]<<"\n";
}
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    pass_time=clock();
    int t=1;
    //cin>>t;
    while(t--)solve();
    pass_time=clock()-pass_time;
    dbg(pass_time/CLOCKS_PER_SEC);
}

• 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