Submission #237677

#	Time	Username	Problem	Language	Result	Execution time	Memory
237677		Half	Pilot (NOI19_pilot)	C++14	89 / 100	1096 ms	61800 KiB

pilot

#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <cmath>

using namespace std;

typedef vector<int> vi;
typedef pair<int,int> pi;
typedef long long ll;

#define loop(i,a,b) for (int i = a; i <= b; i++)

#define INF ((unsigned) ~0)
#define F first
#define S second
#define PB push_back
#define MP make_pair

const int MXN = 1000000;
int n, q;
int a[MXN];
map<pi, int> v;
int sdu[MXN];
int ssz[MXN];
vector<pair<int, ll>> f;

int rp(int x){
    if(sdu[x] == -1)
        return -1;
    if(sdu[x] == x)
        return x;
    if(sdu[sdu[x]] == sdu[x])
        return sdu[x];
    return sdu[x] = rp(sdu[x]);
}

int main(){
    cin >> n >> q;
    for(int i = 0; i < n; i++){
        cin >> a[i];
        v[MP(a[i], i)] = -1;
        sdu[i] = -1;
    }
    f = {};
    f.push_back(MP(0, 0));
    ll sm = 0;
    for(map<pi, int>::iterator it = v.begin(); it != v.end(); it++){
        //cout << sm << "\n";
        /*for(int j = 0; j < n; j++)
            cout << rp(j) << " ";
        cout << "\n";*/
        it->S = 1;
        int i = (it->F).S;
        //cout << i << "\n";
        //cout << v[MP(a[i - 1], i - 1)] << " " << v[MP(a[i + 1], i + 1)] << "\n";
        if(i != 0 && i != n - 1){
            if(v[MP(a[i - 1], i - 1)] == 1 && v[MP(a[i + 1], i + 1)] == 1){
                int sz = ssz[rp(i - 1)] + ssz[rp(i + 1)] + 1;
                sm -= ((ll)ssz[rp(i - 1)])*((ll)ssz[rp(i - 1)] + 1) / (ll)2;
                sm -= ((ll)ssz[rp(i + 1)])*((ll)ssz[rp(i + 1)] + 1) / (ll)2;
                sm += ((ll)sz)*((ll)sz + 1) / (ll)2;
                sdu[rp(i - 1)] = rp(i + 1);
                sdu[i] = rp(i + 1);
                ssz[rp(i + 1)] = sz;

                if((it->F).F != f[f.size() - 1].F){
                    f.push_back(MP((it->F).F, sm));
                }else{
                    f[f.size() - 1].S = sm;
                }
                continue;
            }
        }
        if(i != 0){
            if(v[MP(a[i - 1], i - 1)] == 1){
                //cout << "<\n";
                sdu[i] = rp(i - 1);
                ssz[rp(i - 1)]++;
                sm += ssz[rp(i - 1)];

                if((it->F).F != f[f.size() - 1].F){
                    f.push_back(MP((it->F).F, sm));
                }else{
                    f[f.size() - 1].S = sm;
                }
                continue;
            }
        }
        if(i != n - 1){
            if(v[MP(a[i + 1], i + 1)] == 1){
                //cout << ">\n";
                sdu[i] = rp(i + 1);
                ssz[rp(i + 1)]++;
                sm += ssz[rp(i + 1)];

                if((it->F).F != f[f.size() - 1].F){
                    f.push_back(MP((it->F).F, sm));
                }else{
                    f[f.size() - 1].S = sm;
                }
                continue;
            }
        }
        //cout << "=\n";
        sdu[i] = i;
        ssz[i] = 1;
        sm += 1;
        if((it->F).F != f[f.size() - 1].F){
            f.push_back(MP((it->F).F, sm));
        }else{
            f[f.size() - 1].S = sm;
        }
    }
    while(q--){
        int y;
        cin >> y;
        int lo = 0, hi = f.size();
        while(hi - lo > 1){
            if(f[(hi + lo) / 2].F > y){
                hi = (hi + lo) / 2;
            }else{
                lo = (hi + lo) / 2;
            }
        }
        cout << f[lo].S << "\n";
    }
}

• 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