oj.uz

Submission #632907

# Submission time Handle Problem Language Result Execution time Memory
632907 2022-08-21T07:36:06 Z berr Zamjene (COCI16_zamjene) C++17
84 / 140
 3867 ms 138488 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)%mod;
    }
 

    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 12 ms 8148 KB Output is correct
2 Correct 12 ms 8152 KB Output is correct
3 Correct 11 ms 8112 KB Output is correct

Subtask #2
14.0 / 14.0

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

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 8100 KB Output is correct
2 Correct 12 ms 8276 KB Output is correct
3 Correct 12 ms 8140 KB Output is correct

Subtask #4
14.0 / 14.0

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

Subtask #5
14.0 / 14.0

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

Subtask #6
14.0 / 14.0

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

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 13176 KB Output is correct
2 Correct 99 ms 14912 KB Output is correct
3 Incorrect 168 ms 18064 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1040 ms 47844 KB Output is correct
2 Incorrect 3867 ms 138488 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

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

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 983 ms 62664 KB Output is correct
2 Incorrect 2214 ms 101892 KB Output isn't correct
3 Halted 0 ms 0 KB -