oj.uz

답안 #765191

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
765191 2023-06-24T09:14:12 Z PanosPask Zamjene (COCI16_zamjene) C++14
84 / 140
 1183 ms 73244 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n, Q;
vector<int> a;
vector<vector<int>> cntsort;
vector<int> pos_v;
unordered_map<int, int> num_v;

// DSU variables
vector<ll> total_pos, total_num;
vector<int> rep;
vector<int> sz;
unordered_map<ll, int> diff_looking;

ll q4ans = 0;

int find(int a)
{
    if (rep[a] != a)
        rep[a] = find(rep[a]);

    return rep[a];
}

void remove_option(int a)
{
    a = find(a);

    if (total_num[a] == total_pos[a])
        return;


    ll diff = total_num[a] - total_pos[a];

    int v = diff_looking[diff];
    if (v == sz[a])
        diff_looking.erase(diff);
    else
        diff_looking[diff] -= sz[a];

    if (diff_looking.find(-diff) != diff_looking.end()) {
        int b = diff_looking[-diff];

        q4ans -= (ll)b * sz[a];
    }
}

void add_option(int a)
{
    a = find(a);

    if (total_num[a] == total_pos[a])
        return;

    ll diff = total_num[a] - total_pos[a];


    diff_looking[diff] += sz[a];
    if (diff_looking.find(-diff) != diff_looking.end()) {
        int b = diff_looking[-diff];

        q4ans += (ll)sz[a] * b;
    }
}

void init(void)
{
    rep.resize(n);
    sz.assign(n, 1);

    total_pos.resize(n);
    total_num.resize(n);

    for (int i = 0; i < n; i++) {
        rep[i] = i;
        total_pos[i] = pos_v[i];
        total_num[i] = num_v[a[i]];

        add_option(i);
    }
}

void unite(int a, int b)
{
    a = find(a);
    b = find(b);

    if (a == b)
        return;

    if (sz[b] > sz[a])
        swap(a, b);

    remove_option(a);
    remove_option(b);

    rep[b] = a;
    sz[a] += sz[b];
    total_num[a] += total_num[b];
    total_pos[a] += total_pos[b];

    add_option(a);
}

void change_to(int a, int p_v, int n_v)
{
    a = find(a);

    p_v = num_v[p_v];
    n_v = num_v[n_v];

    remove_option(a);

    total_num[a] += (ll)n_v - p_v;

    add_option(a);
}

int main(void)
{
    scanf("%d %d", &n, &Q);

    srand(77333);

    pos_v.resize(n);
    cntsort.resize(1e6 + 1);
    a.resize(n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
        cntsort[a[i]].push_back(i);
    }

    vector<int> s_a = a;
    sort(s_a.begin(), s_a.end());

    int p_v = -1;
    for (int i = 0; i < n; i++) {
        if (num_v.find(s_a[i]) == num_v.end())
            num_v[s_a[i]] = rand();
        pos_v[i] = num_v[s_a[i]];

    }

    init();

    while (Q--) {
        int op;
        scanf("%d", &op);

        if (op == 1) {
            int p1, p2;
            scanf("%d %d", &p1, &p2);
            p1--; p2--;

            change_to(p1, a[p1], a[p2]);
            change_to(p2, a[p2], a[p1]);

            swap(a[p1], a[p2]);
        }
        else if (op == 2) {
            int p1, p2;
            scanf("%d %d", &p1, &p2);
            p1--; p2--;

            unite(p1, p2);
        }
        else if (op == 3) {
            if (diff_looking.size())
                printf("NE\n");
            else
                printf("DA\n");
        }
        else {
            printf("%lld\n", q4ans);
        }
    }

    return 0;
}

Compilation message

zamjene.cpp: In function 'int main()':
zamjene.cpp:140:9: warning: unused variable 'p_v' [-Wunused-variable]
  140 |     int p_v = -1;
      |         ^~~
zamjene.cpp:125:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  125 |     scanf("%d %d", &n, &Q);
      |     ~~~~~^~~~~~~~~~~~~~~~~
zamjene.cpp:133:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  133 |         scanf("%d", &a[i]);
      |         ~~~~~^~~~~~~~~~~~~
zamjene.cpp:152:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  152 |         scanf("%d", &op);
      |         ~~~~~^~~~~~~~~~~
zamjene.cpp:156:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  156 |             scanf("%d %d", &p1, &p2);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~
zamjene.cpp:166:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  166 |             scanf("%d %d", &p1, &p2);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 23768 KB Output is correct
2 Correct 11 ms 23764 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 11 ms 23764 KB Output is correct
3 Correct 11 ms 23720 KB Output is correct

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 23764 KB Output is correct
2 Correct 12 ms 23764 KB Output is correct
3 Correct 13 ms 23764 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 23764 KB Output is correct
2 Correct 11 ms 23764 KB Output is correct
3 Correct 12 ms 23752 KB Output is correct

Subtask #5
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 23772 KB Output is correct
2 Correct 11 ms 23764 KB Output is correct
3 Correct 11 ms 23832 KB Output is correct

Subtask #6
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 24168 KB Output is correct
2 Correct 15 ms 24216 KB Output is correct
3 Correct 15 ms 24276 KB Output is correct

Subtask #7
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 55 ms 28152 KB Output is correct
2 Correct 62 ms 28364 KB Output is correct
3 Incorrect 67 ms 29056 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 516 ms 47712 KB Output is correct
2 Incorrect 1183 ms 64100 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 822 ms 72876 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 640 ms 67540 KB Output is correct
2 Incorrect 789 ms 73244 KB Output isn't correct
3 Halted 0 ms 0 KB -