Submission #507623

#	Time	Username	Problem	Language	Result	Execution time	Memory
507623		julian33	Zamjene (COCI16_zamjene)	C++14	0 / 140	4682 ms	57596 KiB

zamjene

#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
• Subtask 2: 0 / 14
• Subtask 3: 0 / 14
• Subtask 4: 0 / 14
• Subtask 5: 0 / 14
• Subtask 6: 0 / 14
• Subtask 7: 0 / 14
• Subtask 8: 0 / 14
• Subtask 9: 0 / 14
• Subtask 10: 0 / 14