제출 #652747

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
652747		raysh07	Pilot (NOI19_pilot)	C++14	100 / 100	510 ms	59980 KiB

pilot

#include <bits/stdc++.h>
using namespace std;
#define int long long

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 1e6 + 69;
int sz[maxn];
int root[maxn];
int ans[maxn];
int last = 0;

int findroot(int x)
{
    while (x!=root[x])
    x= root[x];
    return x;
}

void unite(int x, int y, int w)
{
    x = findroot(x);
    y = findroot(y);
    if (sz[x]<sz[y])swap(x, y);
    root[y] = x;
    ans[w] += sz[x]*sz[y];
    sz[x] += sz[y];
}

void Solve() 
{
    int n,q;
    cin>>n>>q;
    vector <pair<int,int>> v;
    for (int i=0; i<n; i++)
    {
        int x;
        cin>>x;
        v.push_back(make_pair(x, i));
    }
    //ans[0] = n;
    sort(v.begin(), v.end());
    for (int i=0; i<maxn; i++)
    {
        ans[i] = 0;
    }
    for (int i=0; i<n+1; i++)
    {
        sz[i] = 0;
        root[i] = i;
    }
    //int last = 0;
    //ans[0] = 0;
    //for (int i=0; i<n; i++)
    //cout<<v[i].first<<" "<<v[i].second<<"\n";
    for (int i=0; i<n; i++)
    {
        int w = v[i].first;
        int x = v[i].second;
        //cout<<x<<"\n";
        sz[x] = 1;
        ans[w] += 1;
        if (x!=0 && sz[x-1]!=0)
        unite(x, x-1, w);
        if (x!=n-1 && sz[x+1]!=0)
        unite(x, x+1, w);
       // for (int j=0; j<n; j++)
       // {
       //     cout<<findroot(j)<<" ";
        //}
        //cout<<"\n";
       // for (int j=0; j<n; j++)
        //{
            //cout<<sz[j]<<" ";
       // }
        //cout<<"\n";
        //cout<<w<<" "<<ans[w]<<"\n";
    }
    int s = 0;
    for (int i=0; i<maxn; i++)
    {
        s+= ans[i];
        ans[i] = s;
    }
    for (int i=0; i<q; i++)
    {
        int h;
        cin>>h;
        cout<<ans[h]<<"\n";
    }
}

int32_t main() 
{
    //freopen(".in",  "r", stdin);
    //freopen(".out", "w", stdout);
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    //cin >> t;
    for(int i = 1; i <= t; i++) 
    {
        //cout << "Case #" << i << ": ";
        Solve();
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
    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