Codeforces Round #791 (Div. 2) 1559 → 1540

https://codeforces.com/contest/1679

Dashboard - Codeforces Round #791 (Div. 2) - Codeforces

!!!! 모든 답은 제 풀이일 뿐 공부를 위한 올바른 정해가 아닐 수 있습니다 !!!!

 

A. AvtoBus

https://codeforces.com/contest/1679/problem/A

Problem - A - Codeforces

문제

 

n이 주어진다. 바퀴가 4개인 버스와 바퀴가 6개인 버스가 있다. 총 바퀴 수가 n일때 최소 버스 수와 최대 버스 수를 구하는 문제

 

풀이

 

4를 최대로 쓴 경우의수와 6을 최대로 쓴 경우의수를 계산해서 출력해준다

 

코드

 

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int T;
    cin >> T;
    while (T--) {
        long long n;
        cin >> n;
        long long div4 = n / 4, div6 = n / 6;
        long long div12 = n / 12;
        long long l = -1, r = -1;
        for (long long i = 0; i <= 10; i++) {
            long long dif = n - 6 * i;
            if (dif >= 0) {
                if (dif % 4 == 0) {
                    l = dif / 4LL + i;
                    break;
                }
            }
        }
        for (long long i = 0; i <= 10; i++) {
            long long dif = n - 4 * i;
            if (dif >= 0) {
                if (dif % 6 == 0) {
                    r = dif / 6LL + i;
                    break;
                }
            }
        }
        if (l == -1 && r == -1)cout << -1 << '\n';
        else {
            if (l == -1) {
                cout << r << ' ' << r << '\n';
            }
            else if (r == -1) {
                cout << l << ' ' << l << '\n';
            }
            else {
                cout << r << ' ' << l << '\n';
            }
        }


    }

}

 

B. Stone Age Problem

https://codeforces.com/contest/1679/problem/B

Problem - B - Codeforces

문제

 

n길이의 배열 a와 ,q개의 쿼리가 주어진다. 쿼리는 아래와 같은 2개의 타입으로 주어진다.

1 : i x (i번째 인덱스의 수를 x로 바꾼다)

2 : x (모든 원소를 x로 바꾼다)

각 쿼리마다 모든 원소의 합을 출력하는 문제

 

풀이

 

처음에는 모든 원소의 합을 구해놓고 인덱스의 원소 값 차이를 구하다가 2쿼리가 나온 이후 map에 사용한 인덱스만 따로 저장하고 나올때마다 map을 초기화시켜주면서 새로 계산해주면 된다.

 

 

코드

 

    #include <bits/stdc++.h>
    using namespace std;
    long long a[200001];
    int main() {
        ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
        long long n, q;
        cin >> n >> q;
        long long sum = 0;
        map<int, bool> Map;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
            sum += a[i];
        }
        long long now = 0;
        while (q--) {
            int type;
            cin >> type;
            if (type == 1) {
                long long idx, val;
                cin >> idx >> val;
                if (now) {
                    if (Map[idx]) {
                        long long dif = a[idx] - val;
                        a[idx] = val;
                        sum -= dif;
                        cout << sum << '\n';
                    }
                    else {
                        long long dif = now - val;
                        a[idx] = val;
                        sum -= dif;
                        cout << sum << '\n';
                        Map[idx] = true;
                    }
                }
                else {
                    long long dif = a[idx] - val;
                    a[idx] = val;
                    sum -= dif;
                    cout << sum << '\n';
                }
            }
            else {
                long long x;
                cin >> x;
                Map.clear();
                now = x;
                sum = x * n;
                cout << sum << '\n';
            }
        }
     
     
    }

C. Rooks Defenders

https://codeforces.com/contest/1679/problem/C

Problem - C - Codeforces

문제

 

n과 q가 주어진다. n*n 공간의 q개의 아래와 같은 쿼리들이 주어진다.

1 x y

2 x y

3 x1 y1 x2 y2

1이라면 x,y에 돌을 추가 2라면 x,y에 돌을 제거 , 3이라면 왼쪽위를 x1, y1 오른쪽아래를 x2,y2로 가지는 subrectangle이 주어진다. subrectangle 이 최소 한개 이상의 돌에게 공격받고 있으면 YES 아니라면 NO를 출력하는 문제 여기서 공격받는다는 의미는 같은 행이나 같은 열을 공유하는것이다.

 

풀이

 

subrectangle의 각 행과 각 열을 세그먼트 트리로 관리하여 돌들의 공격을 받는지 검사한다. 여기서 세그먼트트리의 값은 각 행이나 각 열의 돌 유무이다.

 

 

코드

    #include <bits/stdc++.h>
    using namespace std;
    int row[100001], col[100001];
    bool d1[400001], d2[400001];
    void Update1(int node, int start, int end, int i,int dif) {
        if (start > i || end < i)return;
        if (start == end) {
            row[start] += dif;
            if (row[start])d1[node] = true;
            else d1[node] = false;
            return;
        }
        int mid = (start + end) / 2;
        Update1(node * 2, start, mid, i,dif);
        Update1(node * 2 + 1, mid + 1, end, i,dif);
        d1[node] = (d1[node * 2] && d1[node * 2 + 1]);
    }
    void Update2(int node, int start, int end, int i,int dif) {
        if (start > i || end < i)return;
        if (start == end) {
            col[start] += dif;
            if (col[start])d2[node] = true;
            else d2[node] = false;
            return;
        }
        int mid = (start + end) / 2;
        Update2(node * 2, start, mid, i,dif);
        Update2(node * 2 + 1, mid + 1, end, i,dif);
        d2[node] = (d2[node * 2] && d2[node * 2 + 1]);
    }
    bool query1(int node, int start, int end, int i, int j) {
        if (start > j || end < i)return true;
        if (start >= i && end <= j)return d1[node];
        int mid = (start + end) / 2;
        return (query1(node * 2, start, mid, i, j) && query1(node * 2 + 1, mid + 1, end, i, j));
    }
    bool query2(int node, int start, int end, int i, int j) {
        if (start > j || end < i)return true;
        if (start >= i && end <= j)return d2[node];
        int mid = (start + end) / 2;
        return (query2(node * 2, start, mid, i, j) && query2(node * 2 + 1, mid + 1, end, i, j));
    }
    int main() {
        ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
        long long n, q;
        cin >> n >> q;
        while (q--) {
            int t;
            cin >> t;
            if (t == 1 || t == 2) {
                int x, y;
                cin >> x >> y;
                int dif;
                if (t == 1)dif = 1;
                else dif = -1;
                Update1(1, 1, n, x,dif);
                Update2(1, 1, n, y,dif);
            }
            else {
                int x1, y1, x2, y2;
                cin >> x1 >> y1 >> x2 >> y2;
                bool num1 = query1(1, 1, n, x1, x2);
                bool num2 = query2(1, 1, n, y1, y2);
                //cout << num1 << ' ' << num2 << '\n';
                if (num1 || num2)cout << "Yes\n";
                else cout << "No\n";
            }
        }
     
     
    }

 

 

자세한 설명에 중점을 두기보다는 대회 기록에 중점을 둔 글입니다 !

틀린 부분은 감사히 지적받겠습니다.