제출 #765186

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
765186		PanosPask	Zamjene (COCI16_zamjene)	C++14	84 / 140	1286 ms	84824 KiB

zamjene

#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(2322);

    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;
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 0 / 14
• Subtask 8: 0 / 14
• Subtask 9: 0 / 14
• Subtask 10: 0 / 14