oj.uz

답안 #507623

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
507623 2022-01-12T20:55:35 Z julian33 Zamjene (COCI16_zamjene) C++14
0 / 140
 4682 ms 57596 KB 
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {
    cerr<<vars<<" = ";
    string delim="";
    (...,(cerr<<delim<<values,delim=", "));
    cerr<<"\n";
}
#else
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {}
#endif

#define pb push_back
#define sz(x) (int)(x.size())
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template<typename T> inline void maxa(T& a,T b){a=max(a,b);}
template<typename T> inline void mina(T& a,T b){a=min(a,b);} 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

#ifdef LOCAL
const int mxN=50;
#else
const int mxN=1e6+5; //make sure this is right
#endif
const int mod=1e9+7;
const int b=131;

ll fpow(ll b,ll e){
    ll res=1;
    while(e){
        if(e&1)
            res=(res*b)%mod;
        b=(b*b)%mod;
        e>>=1;
    }
    return res;
}

ll divmod(ll a,ll b){
    return (a*fpow(b,mod-2))%mod;
}

map<int,ll> cnt;

ll uf[mxN],hp[mxN],hq[mxN],ans,sub;
int tot,bad[mxN];

int find(int x){return uf[x]<0?x:uf[x]=find(uf[x]);}

void add2(int id,ll v,int x){
    if(id==0) return;
    id=(id+mod)%mod;
    ll s=abs(uf[x]);
    ans-=cnt[id]*(cnt[id]-1)/2;
    cnt[id]+=v*s;
    sub+=(s*(s-1)/2)*v;
    if(!cnt[id]) cnt.erase(id);
    else ans+=cnt[id]*(cnt[id]-1)/2;
}

void add(int x,int idx,int v){
    add2(hp[x]-hq[x],-1,x);
    add2(hq[x]-hp[x],-1,x);
    ll exp=fpow(b,idx)*v;
    hp[x]=(hp[x]+exp+mod)%mod;
    add2(hp[x]-hq[x],1,x);
    add2(hq[x]-hp[x],1,x);
}

void unite(int x,int y){
    x=find(x); y=find(y);
    if(x==y) return;
    if(uf[x]>uf[y]) swap(x,y);
    tot-=bad[x]; tot-=bad[y];
    add2(hp[x]-hq[x],-1,x);
    add2(hq[x]-hp[x],-1,x);
    add2(hp[y]-hq[y],-1,y);
    add2(hq[y]-hp[y],-1,y);
    uf[x]+=uf[y]; uf[y]=x;
    hp[x]=(hp[x]+hp[y])%mod;
    hq[x]=(hq[x]+hq[y])%mod;
    bad[x]=(hp[x]!=hq[x]);
    tot+=bad[x];
    add2(hp[x]-hq[x],1,x);
    add2(hq[x]-hp[x],1,x);
}

/*
hp[i] + hp[j] = hq[i] + hq[j]
hp[i] - hq[i] = hq[j] - hp[j]
*/

int a[mxN],s[mxN];

ll calc(int x){
    return abs(uf[x])*(abs(uf[x])-1)/2;
}

int main(){
    cin.sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    #ifdef LOCAL
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
    #endif

    int n,q; cin>>n>>q;
    memset(uf,-1,sizeof(uf));
    for(int i=1;i<=n;i++){
        cin>>a[i];
        hp[i]=fpow(b,a[i]);
        s[i]=a[i];
    }
    sort(s+1,s+1+n);
    for(int i=1;i<=n;i++){
        hq[i]=fpow(b,s[i]);
        bad[i]=(hp[i]!=hq[i]);
        tot+=bad[i];
        add2(hq[i]-hp[i],1,i);
        add2(hp[i]-hq[i],1,i);
    }
    while(q--){
        int op; cin>>op;
        if(op==1){
            int i,j; cin>>i>>j;
            if(find(i)==find(j)) continue;
            int x=find(i); int y=find(j);
            tot-=bad[x]; tot-=bad[y];
            add(x,a[i],-1);
            add(y,a[j],-1);
            swap(a[i],a[j]);
            add(x,a[i],1);
            add(y,a[j],1);
            bad[x]=(hp[x]!=hq[x]);
            bad[y]=(hp[y]!=hq[y]);
            tot+=bad[x]; tot+=bad[y];
        } else if(op==2){
            int i,j; cin>>i>>j;
            unite(i,j);
        } else if(op==3){
            cout<<(tot?"NE\n":"DA\n");
        } else{
            cout<<(ans-sub)/2<<"\n";
        }
    }
}

Subtask #1
0 / 14.0

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

Subtask #2
0 / 14.0

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

Subtask #3
0 / 14.0

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

Subtask #4
0 / 14.0

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

Subtask #5
0 / 14.0

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

Subtask #6
0 / 14.0

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

Subtask #7
0 / 14.0

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

Subtask #8
0 / 14.0

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

Subtask #9
0 / 14.0

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

Subtask #10
0 / 14.0

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