Submission #1188723

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188723		vusal	Pilot (NOI19_pilot)	C++20	89 / 100	1094 ms	126664 KiB

pilot

#include <bits/stdc++.h>

//author : vusal

using namespace std;

#define int long long

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MOD = 1e9 + 7;
const int oo = 1e18 + 100;
const int sz = 1e6 + 7;

vector<int>g[sz];
vector<int>mp[sz];
vector<int>ans(sz);

void _()
{
    int n, q;
    cin >> n >> q;

    set<int>s;

    vector<int>v(n + 2);

    for(int i = 1; i <= n; i++)
    {
        cin >> v[i];
        mp[v[i]].push_back(i);
    }

    for(int i = 0; i <= n + 1; i++)
    {
        s.insert(i);
    }

    int sum = 0;

    for(int y = 0; y < sz; y++)
    {
        for(int i : mp[y])
        {
            s.erase(i);
            auto itr = s.lower_bound(i);
            int j = (*itr);
            --itr;
            int k = (*itr);
            int d1 = (i - k - 1);
            int d2 = (j - i - 1);
            int d3 = (j - k - 1);
            sum -= d1 * (d1 + 1) / 2;
            sum -= d2 * (d2 + 1) / 2;
            sum += d3 * (d3 + 1) / 2;
        } 
        ans[y] = sum;  
    }

    while(q--)
    {
        int x;
        cin >> x;
        cout << ans[x] << endl;
    }
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
// cin >> t;
    while(t--)
    {
        _();
    }
}

• 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: 0 / 11