본문 바로가기

코드포스

[코드포스 Practice13] A. Kuriyama Mirai's Stones

문제 풀 때 저게 너무 궁금했다.

문제랑 상관없을 것 같아서 바로 패스하고 코딩했는데 지금은 시간 많으니 걍 친구한테 물어봤다. 

불쾌하다? 그런거라는데 음.. 

그렇구나

 

이거 딱 보자마자 그 부분합이었나? 그거 떠올랐다. 

부분합? 음 명칭이 이게 맞군

합을 구해놓으면 밑의 m개의 쿼리에서 그대로 갖다쓰기만 하면 끝~~

질문이 2개라 문제 따라 배열을 2개 만들어줬다. 하나는 그냥 배열 하나는 정렬한 배열

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
 
using namespace std;
using i64 = long long;
 
int main() {
    int n, m;
    scanf("%d", &n);
    vector <i64> v1(n + 1, 0);
    vector <i64> v2(n + 1, 0);
    for(int i = 1; i <= n; i++)
    {
        scanf("%lld", &v1[i]);
        v2[i] = v1[i];
    }
    scanf("%d", &m);
    sort(v2.begin(), v2.end());
    for(int i = 1; i <= n; i++)
    {
        v1[i] += v1[i - 1];
        v2[i] += v2[i - 1];
    }
    for(int i = 0; i < m; i++)
    {
        int type, l, r;
        scanf("%d %d %d", &type, &l, &r);
        if (type == 1)
            printf("%lld\n", v1[r] - v1[l-1]);
        else
            printf("%lld\n", v2[r] - v2[l-1]);
    }
    return 0;
}

ㅋㅋ

풀면서 실력 부족하다 느꼈던 게 부분합 0번째 인덱스 0으로 주면 편한데 그걸 생각 못해서 0번째 인덱스 일 때 조건 따로 뺴려고 했었다. 

 

sum[1].resize(n + 1);

 

아 이건 북님 코드에서 본건데 이렇게 .resize()를 하면 그 크기만큼 사이즈가 조정된다.

 

    vector<i64> sum[3];

    sum[1].resize(n + 1);

    for (int i = 1; i <= n; i++)
        sum[1][i] = sum[1][i - 1] + arr[i];

신기~ resize해서 이차원 배열 접근하듯이 할 수 있구나