Submission #1181807

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181807		den1z19	Mountains (NOI20_mountains)	C++17	66 / 100	2095 ms	7240 KiB

Mountains

#include "bits/stdc++.h"
#include <vector>

using std::cout, std::cin, std::vector, std::string;

long long int left=0,right=0;
long long int n,tmp,count=0;
vector<std::pair<long long int, long long int>> h;
vector<long long int > dp;
long long int j,i,last=0;


void insertSorted(std::vector<long long int>& vec, int value) {
    auto it = std::lower_bound(vec.begin(), vec.end(), value);
    vec.insert(it, value);
}
void insertSorted(std::vector<long long int>& vec, int value, int& multi) {
    auto it = std::lower_bound(vec.begin(), vec.end(), value);
    vec.insert(it, value);
    multi++;
}

void solve(){
cin >> n;
dp.clear();
dp.reserve(n);
h.clear();
h.reserve(n);
count=0;
for (long long int i =0; i<n;i++){
    cin>>tmp;
    auto it = upper_bound(
        h.begin(), h.end(),
        std::make_pair(tmp, i),
        [](auto &a, auto &b){
            return a.first < b.first;
        }
    );
    h.insert(it, std::make_pair(tmp, i));
}



int multi =0;
insertSorted(dp, h[0].second,multi);
insertSorted(dp, h[1].second,multi);
if (h[1].first != h[0].first) multi=1;
insertSorted(dp, h[2].second,multi);
if (h[2].first != h[1].first) multi=1;

auto it = std::lower_bound(dp.begin(), dp.end(), h[2].second);
int index = std::distance(dp.begin(), it);

left= std::max(0,index-multi+1);
right=dp.size()-multi-left;
count=right*left;

for (i=3; i<n ;i++){
    left=right=0;
    insertSorted(dp, h[i].second,multi);
    if (h[i].first != h[i-1].first) multi=1;
    auto it = std::lower_bound(dp.begin(), dp.end(), h[i].second);
    int index = std::distance(dp.begin(), it);
    left= std::max(0,index-multi+1);
    right=dp.size()-multi-left;
    count+=right*left;
    



}

cout << count << '\n';
}

int main(){
std::ios::sync_with_stdio(false);
cin.tie(nullptr);
unsigned long long ct =1;
// cin >> ct;
while(ct--) solve();
    

}

• Subtask 1: 2 / 2
• Subtask 2: 0 / 4
• Subtask 3: 0 / 9
• Subtask 4: 36 / 36
• Subtask 5: 28 / 28
• Subtask 6: 0 / 9
• Subtask 7: 0 / 12