백준 6217, AdHoc
USACO January 2007 Contest Silver 2번 문제.
중복되는 구간이 있을 수 있다는 것을 생각하지 못했다.
구간 $[a:b]$ 가 있을 때, $a+1$ 에서 $b-1$ 까지 모두 마킹 할 필요가 없다는 것도 알 수 있었다.
Source Code
//BOJ6217
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
vector<pii> input;
int seestack[10010];
int N, I, H, R;
bool comp(pii& a, pii& b) {
if (a.first < b.first) return true;
if (a.first == b.first && a.second < b.second) return true;
return false;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> N >> I >> H >> R;
for (int i = 0; i < R; ++i) {
int a, b;
cin >> a >> b;
if (a > b) swap(a, b);
input.push_back({ a,b });
}
sort(input.begin(), input.end(), comp);
for (int i = 0; i < R; ++i) {
if (i > 0 && input[i] == input[i - 1]) continue;
if (input[i].second - input[i].first < 2) continue;
--seestack[input[i].first + 1];
++seestack[input[i].second];
}
int cnt = 0;
for (int i = 1; i <= N; ++i) {
cnt += seestack[i];
printf("%d\n", H + cnt);
}
return 0;
}