Submission #765147

#	Time	Username	Problem	Language	Result	Execution time	Memory
765147		PanosPask	Zamjene (COCI16_zamjene)	C++14	0 / 140	952 ms	87492 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
int total_looking = 0;
vector<ll> total_pos, total_num;
vector<int> pair_to;
vector<int> rep;
vector<int> sz;

ll q4ans = 0;

unordered_map<ll, int> diff_looking;

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

    return rep[a];
}

void remove_option(int a)
{
    if (total_num[a] == total_pos[a])
        return;

    a = find(a);

    diff_looking.erase(total_num[a] - total_pos[a]);
    if (pair_to[a] != -1) {
        int b = pair_to[a];
        pair_to[b] = pair_to[a] = -1;

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

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

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

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

        pair_to[b] = a;
        pair_to[a] = b;

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

void init(void)
{
    rep.resize(n);
    sz.assign(n, 1);
    pair_to.resize(n);
    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]];
        pair_to[i] = -1;

        if (total_num[i] != total_pos[i]) {
            total_looking++;
            add_option(i);
        }
    }
}

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

    if (total_num[a] != total_pos[a])
        total_looking--;
    if (total_num[b] != total_pos[b])
        total_looking--;

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

    if (total_num[a] != total_pos[a])
        total_looking++;
}

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

    if (total_num[a] == total_pos[a])
        total_looking++;

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

    remove_option(a);

    total_num[a] += n_v - p_v;

    add_option(a);

    if (total_num[a] == total_pos[a])
        total_looking--;
}

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

    srand(2222);

    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 (total_looking)
                printf("NE\n");
            else
                printf("DA\n");
        }
        else {
            printf("%lld\n", q4ans);
        }
    }

    return 0;
}

Compilation message (stderr)

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

• Subtask 1: 0 / 14
• Subtask 2: 0 / 14
• Subtask 3: 0 / 14
• Subtask 4: 0 / 14
• Subtask 5: 0 / 14
• Subtask 6: 0 / 14
• Subtask 7: 0 / 14
• Subtask 8: 0 / 14
• Subtask 9: 0 / 14
• Subtask 10: 0 / 14