oj.uz

Submission #633003

# Submission time Handle Problem Language Result Execution time Memory
633003 2022-08-21T11:51:37 Z berr Zamjene (COCI16_zamjene) C++17
0 / 140
 1941 ms 97800 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=100000002181, 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

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

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 8148 KB Output is correct
2 Incorrect 11 ms 8148 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

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

Subtask #4
0 / 14.0

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

Subtask #5
0 / 14.0

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

Subtask #6
0 / 14.0

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

Subtask #7
0 / 14.0

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

Subtask #8
0 / 14.0

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

Subtask #9
0 / 14.0

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

Subtask #10
0 / 14.0

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