오아시스 재결합
문제
오아시스의 재결합 공연에 N명이 한 줄로 서서 기다리고 있다.
이 역사적인 순간을 맞이하기 위해 줄에서 기다리고 있던 백준이는 갑자기 자기가 볼 수 있는 사람의 수가 궁금해졌다.
두 사람 A와 B가 서로 볼 수 있으려면, 두 사람 사이에 A 또는 B보다 키가 큰 사람이 없어야 한다.
줄에 서 있는 사람의 키가 주어졌을 때, 서로 볼 수 있는 쌍의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000)
둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 231 나노미터 보다 작다.
사람들이 서 있는 순서대로 입력이 주어진다.
출력
서로 볼 수 있는 쌍의 수를 출력한다.
1
2
3
4
5
6
7
8
9
10
11
12
예제 입력 1
7
2
4
1
2
2
5
1
예제 출력 1
10
풀이
처음에는 우선순위 큐로 접근해야하나? 싶었는데 구현해보니 아닌 것 같다.
좀 더 간단하게 큐나 벡터 원소를 뺐다 넣었다 계산하면서도 풀리는 것 같았다.
새로 사람을 넣을 때 가장 최근 사람보다 크면 이미 서 있던 사람들 중 새로운 사람보다 작으면 더 이상 볼 수 없다.
만약 같으면 새로운 사람은 자신과 키가 같은 사람 + 1만큼만 볼 수 있다.
작다면 가장 앞의 한 명 밖에 보지 못 한다.
같은 키를 가진 사람을 pair<int, int>를 통해 묶어 보려고 했는데 잘 되지 않아서 이분 탐색을 이용했다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <iostream>
#include <vector>
#include <string>
#include <functional>
#include <queue>
#include <set>
#include <algorithm>
#include <math.h>
using namespace std;
int dx[4] = {0,0,-1,1};
int dy[4] = {1,-1,0,0};
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int a, b, c, d;
int n, m, t;
cin >> n;
long long ans = 0;
vector<int> v;
for(int i=0;i<n;i++){
cin >> m;
if(v.size()==0){
}
else{
if(m>v[v.size()-1]){
int l = 0, r = v.size()-1;
while(l+1<r){
int mid = (l+r)>>1; //내림차 순으로 정렬되어 있음.
if(v[mid]<=m) r = mid;
else l = mid;
}
ans += (v.size() - l);
while(v.size() && v[v.size()-1] < m){
v.pop_back();
}
}
else if(m==v[v.size()-1]){
int l = 0, r = v.size()-1;
while(l+1<r){
int mid = (l+r)>>1; //내림차 순으로 정렬되어 있음.
if(v[mid]==m) r = mid;
else l = mid;
}
ans += (v.size() - l);
}
else if(m<v[v.size()-1]){
ans +=1;
}
}
v.push_back(m);
// for(int i=0;i<v.size();i++){
// cout << v[i] << ' ';
// }cout << '\n';
// cout << "ans : " << ans << '\n';
}
cout << ans;
return 0;
}