Submission #632906

#	Time	Username	Problem	Language	Result	Execution time	Memory
632906		berr	Zamjene (COCI16_zamjene)	C++17	140 / 140	4766 ms	200132 KiB

zamjene

#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 / 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