oj.uz

답안 #632905

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
632905 2022-08-21T07:30:40 Z berr Zamjene (COCI16_zamjene) C++17
0 / 140
 2115 ms 109304 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;

int sum(int a, int b)
{
    if(a+b>mod) return(a+b)-mod;
    return(a+b);
}

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]=sum(ind[p], sgn*poww[pos]);
    val[p]=sum(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
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 12 ms 8148 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 8192 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 12 ms 8148 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 12 ms 8148 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 8148 KB Output is correct
2 Incorrect 12 ms 8216 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 16 ms 8844 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 72 ms 14416 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1214 ms 60004 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2115 ms 109304 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 942 ms 74756 KB Output isn't correct
2 Halted 0 ms 0 KB -