Submission #1187265

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187265		TheSahib	Pilot (NOI19_pilot)	C++20	100 / 100	520 ms	106572 KiB

pilot

#pragma GCC optimize("O3")
#pragma GCC target("avx2")

#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <vector>
#include <iomanip>
#include <algorithm>
#include <cstring>
#include <array>
#include <string>
#include <stack>


using namespace std;
 
#define ll long long
#define int ll
#define all(v) v.begin(), v.end()
#define pii pair<int, int>

const int MAX = 1e6 + 100, MOD = 1e9 + 7;

vector<int> v[MAX];
vector<int> mp[MAX];
int ANS[MAX];

void solve(){
    int n, q; cin >> n >> q;
    int arr[n + 2];
    int nxt[n + 2];
    int prv[n + 2];
    for(int i = 1; i <= n; ++i){
        cin >> arr[i];
        mp[arr[i]].push_back(i);
    }
    int ans = 0;
    for(int i = 1; i <= n; ++i){
        prv[i] = i - 1;
        nxt[i] = i + 1;
    }
    for(int y = 0; y < MAX; ++y){
        for(int i:mp[y]){
            int j = nxt[i];
            int k = prv[i];
            nxt[k] = j;
            prv[j] = k;

            int d1 = (i - k - 1);
            int d2 = (j - i - 1);
            int d3 = (j - k - 1);
            ans -= d1 * (d1 + 1) / 2;
            ans -= d2 * (d2 + 1) / 2;
            ans += d3 * (d3 + 1) / 2;
        }
        ANS[y] = ans;
    }
    for(int i = 0; i < q; ++i){
        int y; cin >> y;
        cout << ANS[y] << '\n';
    }
}

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

• 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