oj.uz

Submission #632906

# Submission time Handle Problem Language Result Execution time Memory
632906 2022-08-21T07:35:16 Z berr Zamjene (COCI16_zamjene) C++17
140 / 140
 4766 ms 200132 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long

const int N=1e6+37;
int par[N], val[N], ind[N], pairs, poww[N], a[N], s[N], countt[N];
int hashh=1e6+37, mod=1e9+7, q, n;
map<int, int> diff;


void add(int a, int b, int x)
{
    if(b!=0)
    {
        pairs+=a*x*diff[-b];
    }
    diff[b]+=a*x;   
}


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

void add2(int sgn, int p, int pos, int x)
{
    ind[p]+= sgn*poww[pos];
    val[p]+=sgn*poww[x];
    countt[p]+=sgn;
}


void dsu(int x, int y)
{
    x=find(x); y=find(y);

    if(x==y) return;

    add(-1, ind[x]-val[x], countt[x]);   
    add(-1, ind[y]-val[y], countt[y]);

    par[y]=x;
    ind[x]+=ind[y];
    val[x]+=val[y];
    countt[x]+=countt[y];

    add(1, ind[x]-val[x], countt[x]);

}

int32_t main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);

    cin>>n>>q;

    for(int i=0; i<n; i++)
    {
        cin>>a[i];
        s[i]=a[i];
        par[i]=i;   
        countt[i]=1;
    }
    poww[0]=1;
    for(int i=1 ; i<N; i++)
    {
        poww[i]=(poww[i-1]*hashh);
    }
 

    sort(s, s+n);

    for(int i=0; i<n; i++)
    {
        ind[i]=poww[s[i]];
        val[i]=poww[a[i]];
        add(1, ind[i] - val[i], countt[i]);
    }

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

        if(type==1)
        {
            int x, y; cin>>x>>y;
            x--; y--;
            int px=find(x), py=find(y);

            if(px==py)
            {
                swap(a[x], a[y]);
                continue;
            }

            add(-1, ind[px]-val[px], countt[px]);   
            add(-1, ind[py]-val[py], countt[py]);
            add2(-1, px, x, a[x]);
            add2(-1, py, y, a[y]);
            
            swap(a[x], a[y]);

            add2(1, px, x, a[x]);
            add2(1, py, y, a[y]);

            add(1, ind[px]-val[px], countt[px]);   
            add(1, ind[py]-val[py], countt[py]);
    
            
        }
        if(type==2)
        {
            int x, y; cin>>x>>y;
            x--; y--;
            dsu(x, y);
        }
        if(type==3)
        {
            if(diff[0]==n) cout<<"DA\n";
            else cout<<"NE\n";
        }
        if(type==4)
        {
            cout<<pairs<<"\n";
        }
    }


}

Subtask #1
14.0 / 14.0

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

Subtask #2
14.0 / 14.0

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

Subtask #3
14.0 / 14.0

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

Subtask #4
14.0 / 14.0

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

Subtask #5
14.0 / 14.0

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

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8708 KB Output is correct
2 Correct 9 ms 8784 KB Output is correct
3 Correct 10 ms 8892 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 13188 KB Output is correct
2 Correct 92 ms 16020 KB Output is correct
3 Correct 132 ms 19176 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1054 ms 47784 KB Output is correct
2 Correct 4054 ms 148860 KB Output is correct
3 Correct 4766 ms 200132 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2070 ms 97016 KB Output is correct
2 Correct 3500 ms 130360 KB Output is correct
3 Correct 1577 ms 119016 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 875 ms 62672 KB Output is correct
2 Correct 2340 ms 113340 KB Output is correct
3 Correct 1522 ms 119008 KB Output is correct