[Special Round 2] C. 작업 일지

 

저번 주에 비슷한 문제를 푼 적 있어서 쉽게 풀 줄 알았는데 어려웠다ㅠ subtask 다 맞기를 생각했는데 나중에는 포기하고 30점만 맞추려고 호다닥 코드 짰다. 

 

이 문제의 어려운 점은 시작구간과 끝나는 구간의 값이 1, 2, 3, 4 이렇게 변한다는 점인데, 처음에는 구간에 해당하는 개수를 구한 다음 그 개수만큼 계속 더해나갈 생각이었다. 하지만 이러면 끝나는 지점을 알 수 없어서 결국 모든 점을 다 확인하는 방식으로 구현했다. 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#define xx first
#define yy second
 
using namespace std;
using i64 = long long;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;
 
int main() {
    int n, k;
    scanf("%d %d", &n, &k);
    
    vector<ii> v(n);
    for (int i = 0; i < n; i++)
    {
        scanf("%d %d", &v[i].xx, &v[i].yy);
    }
    
    
    int num = 0;
    int ans = 0;
    
    vector<int> va(k+1);
    for (int i = 1; i <= k; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (v[j].xx == i)
            {
                num++;
            }
        }
        
        ans += num;
        printf("%d ", ans);
        
        for (int j = 0; j < n; j++)
        {
            if (v[j].yy == i)
            {
                num--;
                ans -= v[j].yy - v[j].xx + 1;
            }
        }
    }
    
    return 0;
}

 

위처럼 구현했다. 구간이 시작하면 num을 세어주고 출력한 다음 끝나는 구간을 만나면 num을 감소시키고 마지막 값을 빼준다. 

 

이 다음 모든 값들을 확인하는 부분을 어떻게하면 빨리할 수 있을지 생각해봤는데 도저히 떠오르는 게 없어서 포기했다. 

 

 

와... 이거 기울기 개념으로 생각하면 쉽게 풀린다. 저 부분합이 미분한 것과 같아서 두 번 부분합 만들면 답을 쉽게 구할 수 있음. 기울기라니 기발해서 이마를 치게 된다. (물론 실제로 치지는 않음)

 

#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>
#include <bitset>
#include <map>
#include <set>
#include <tuple>
#include <string.h>
#include <math.h>
#include <random>
#include <functional>
#include <assert.h>
#include <math.h>
#define all(x) (x).begin(), (x).end()
#define xx first
#define yy second

using namespace std;

template<typename T, typename Pr = less<T>>
using pq = priority_queue<T, vector<T>, Pr>;
using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;

int main()
{
	int n, k;
	scanf("%d %d", &n, &k);
	
	vector<i64> v(k+5, 0);
	for (int i = 0; i < n; i++)
	{
	    int s, e;
	    scanf("%d %d", &s, &e);
	    
	    v[s] += 1;
	    v[e+1] -= e - s + 2;
	    v[e+2] += e - s + 1;
	}
	
	for (int i = 1; i <= k; i++)
	    v[i] = v[i-1] + v[i];
	    
	for (int i = 1; i <= k; i++)
	    v[i] = v[i-1] + v[i];
	
	for (int i = 1; i <= k; i++)
	    printf("%lld ", v[i]);
    
	return 0;
}

 

부분합 계속 더해나가니 오버플로우 조심!