oj.uz

Submission #765295

# Submission time Handle Problem Language Result Execution time Memory
765295 2023-06-24T10:30:20 Z PanosPask Zamjene (COCI16_zamjene) C++14
84 / 140
 1188 ms 58440 KB 
#include <bits/stdc++.h>
#define POSITIVE_M(v) (v = ((v%MOD) + MOD) % MOD)

using namespace std;

typedef long long ll;
typedef __int128_t lll;

const ll MOD = (1ll << 61) - 1;
const int PRIME = 3;

int n, Q;
vector<int> a;
vector<ll> pos_v;
vector<ll> 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);


    ll diff = total_num[a] - total_pos[a];
    POSITIVE_M(diff);

    if (diff == 0)
        return;

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

    ll rev = -diff;
    POSITIVE_M(rev);

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

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

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

    ll diff = total_num[a] - total_pos[a];
    POSITIVE_M(diff);
    if (diff == 0)
        return;

    diff_looking[diff] += sz[a];

    ll rev = -diff;
    POSITIVE_M(rev);

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

        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];
    POSITIVE_M(total_num[a]);
    total_pos[a] += total_pos[b];
    POSITIVE_M(total_num[b]);

    add_option(a);
}

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

    remove_option(a);

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

    add_option(a);
}

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

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

    srand(42);

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

    ll p_sum = 0;
    for (int i = 0; i < n; i++) {
        if (num_v[s_a[i]] == -1) {
            num_v[s_a[i]] = rand() % MOD;
            POSITIVE_M(num_v[s_a[i]]);
        }
        pos_v[i] = num_v[s_a[i]];
        p_sum += pos_v[i];
        POSITIVE_M(p_sum);
    }

    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:137:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  137 |     scanf("%d %d", &n, &Q);
      |     ~~~~~^~~~~~~~~~~~~~~~~
zamjene.cpp:143:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  143 |         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
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8148 KB Output is correct
2 Correct 3 ms 8148 KB Output is correct
3 Correct 3 ms 8148 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8148 KB Output is correct
2 Correct 3 ms 8148 KB Output is correct
3 Correct 3 ms 8112 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8148 KB Output is correct
2 Correct 3 ms 8148 KB Output is correct
3 Correct 3 ms 8148 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8148 KB Output is correct
2 Correct 4 ms 8148 KB Output is correct
3 Correct 4 ms 8148 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8148 KB Output is correct
2 Correct 4 ms 8112 KB Output is correct
3 Correct 4 ms 8116 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8628 KB Output is correct
2 Correct 7 ms 8660 KB Output is correct
3 Correct 7 ms 8660 KB Output is correct

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 13364 KB Output is correct
2 Correct 59 ms 13788 KB Output is correct
3 Incorrect 63 ms 14536 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 601 ms 34432 KB Output is correct
2 Incorrect 1188 ms 49596 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 800 ms 58440 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 657 ms 54244 KB Output is correct
2 Incorrect 857 ms 58068 KB Output isn't correct
3 Halted 0 ms 0 KB -