Submission #1179520

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179520		InvMOD	Zamjene (COCI16_zamjene)	C++20	140 / 140	2570 ms	98028 KiB

zamjene

#include <bits/stdc++.h>

using namespace std;

#define sz(v) (int)(v).size()
#define all(v) (v).begin(), (v).end()
#define compact(v) (v).erase(unique(all(v)), (v).end())

#define FOR(i, a, b) for(int i = (a); i <= (b); i++)

using ll = long long;

const int N = 1e6 + 5;

mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
ll Rand(ll l, ll r){return uniform_int_distribution<ll>(l, r)(rd);}

int n, q, a[2][N], par[N], sz[N], bad;

ll hsh[N], sum_hsh[2][N], answer;

map<ll, ll> hsh_counter;

ll cnt_hsh(ll pref){
    return (pref != 0 && hsh_counter.count(pref) ? hsh_counter[pref] : 0ll);
}

int asc(int x){
    return x == par[x] ? x : par[x] = asc(par[x]);
}

void upd_cnt(int x, int op){
    if(sum_hsh[0][x] != sum_hsh[1][x]){
        ll cur_sz = sz[asc(x)];
        ll target = sum_hsh[1][x] - sum_hsh[0][x];

        answer = answer + op * cur_sz * cnt_hsh(target);
        hsh_counter[-target] += op * cur_sz;
    }
}

void check_bad(int x, int op){
    bad = bad + op * (sum_hsh[0][x] != sum_hsh[1][x]);
}

void preprocess(){
    FOR(i, 1, n){
        par[i] = i, sz[i] = 1;
        sum_hsh[0][i] += hsh[a[0][i]];
        sum_hsh[1][i] += hsh[a[1][i]];

        check_bad(i, +1), upd_cnt(i, +1);
    }
}

bool join(int u, int v){
    u = asc(u), v = asc(v);
    if(u != v){
        if(sz[u] < sz[v]) swap(u, v);

        upd_cnt(u, -1), upd_cnt(v, -1);
        check_bad(u, -1), check_bad(v, -1);

        sum_hsh[0][u] += sum_hsh[0][v];
        sum_hsh[1][u] += sum_hsh[1][v];
        par[v] = u, sz[u] += sz[v];

        check_bad(u, +1), upd_cnt(u, +1);
        return true;
    }
    return false;
}

void update_pos(int x, int y){
    int par_x = asc(x), par_y = asc(y);

    if(par_x == par_y){
        swap(a[0][x], a[0][y]);
    }
    else{
        upd_cnt(par_x, -1), upd_cnt(par_y, -1);
        check_bad(par_x, -1), check_bad(par_y, -1);
        sum_hsh[0][par_x] -= hsh[a[0][x]];
        sum_hsh[0][par_y] -= hsh[a[0][y]];

        swap(a[0][x], a[0][y]);

        sum_hsh[0][par_x] += hsh[a[0][x]];
        sum_hsh[0][par_y] += hsh[a[0][y]];
        upd_cnt(par_x, +1), upd_cnt(par_y, +1);
        check_bad(par_x, +1), check_bad(par_y, +1);
    }
}

void solve()
{
    cin >> n >> q;
    FOR(i, 1, n){
        cin >> a[0][i];
        a[1][i] = a[0][i];
    }
    sort(a[1] + 1, a[1] + 1 + n);

    vector<int> comp;
    FOR(i, 1, n) comp.emplace_back(a[0][i]);

    sort(all(comp)), compact(comp);
    FOR(i, 1, n){
        a[0][i] = lower_bound(all(comp), a[0][i]) - comp.begin() + 1;
        a[1][i] = lower_bound(all(comp), a[1][i]) - comp.begin() + 1;
    }

    FOR(i, 1, sz(comp)) hsh[i] = Rand(1, 1e13);

    preprocess();

    while(q--){
        int op; cin >> op;

        if(op == 1){
            int a,b; cin >> a >> b;
            update_pos(a, b);
        }
        else if(op == 2){
            int a,b; cin >> a >> b;
            join(a, b);
        }
        else if(op == 3){
            cout << (!bad ? "DA" : "NE") << "\n";
        }
        else cout << answer << "\n";
    }
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    #define name "InvMOD"
    if(fopen(name".INP", "r")){
        freopen(name".INP","r",stdin);
        freopen(name".OUT","w",stdout);
    }

    int t = 1; //cin >> t;
    while(t--) solve();
    return 0;
}

Compilation message (stderr)

zamjene.cpp: In function 'int main()':
zamjene.cpp:143:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  143 |         freopen(name".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
zamjene.cpp:144:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  144 |         freopen(name".OUT","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• 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: 14 / 14
• Subtask 8: 14 / 14
• Subtask 9: 14 / 14
• Subtask 10: 14 / 14