Submission #329197

#	Time	Username	Problem	Language	Result	Execution time	Memory
329197		Mahdi_Shokoufi	Pilot (NOI19_pilot)	C++17	89 / 100	1102 ms	69448 KiB

pilot

//In The Name of Allah
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair < int , int > pii;
typedef pair < ll , ll > pll;

#define X first
#define Y second
#define mp make_pair
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x.size())

const int N = 1e6 + 10;
const ll mod = 1e9 + 7;
const int inf = 1e9 + 10;

int a[N]; ll res[N];
vector < int > pos[N];
set < pii > seg;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    ll n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; i ++)
        cin >> a[i], pos[a[i]].pb(i);
    ll tot = n * (n + 1) / 2;
    seg.insert(mp(n, 1));
    for (int i = N - 10; i > 0; i --){
        res[i] = tot;
        for (int x : pos[i]){
            auto itr = seg.lower_bound(mp(x, -inf));
            ll l = itr -> Y, r = itr -> X;
            tot -= (r - l + 1) * (r - l + 2) / 2;
            tot += (x - l) * (x - l + 1) / 2;
            tot += (r - x) * (r - x + 1) / 2;
            seg.erase(itr);
            if (l < x)
                seg.insert(mp(x - 1, l));
            if (x < r)
                seg.insert(mp(r, x + 1));
        }
    }
    for (int i = 0; i < q; i ++){
        int x;
        cin >> x;
        cout << res[x] << '\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: 0 / 11