oj.uz

Submission #132388

# Submission time Handle Problem Language Result Execution time Memory
132388 2019-07-18T19:12:11 Z nikolapesic2802 Zamjene (COCI16_zamjene) C++14
140 / 140
 1414 ms 330956 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#define ll long long
#define pb push_back

using namespace std;

__gnu_pbds::gp_hash_table<ll,int> cnt;

const int N=1e6+1;
const ll mod=8473968574039; //just a random large number
vector<int> par(N),siz(N,1),p,q;
vector<ll> pwr(1,1),hsh(N);
int n,qq;
ll ans4;
int ans3;
ll mul(ll a,ll b)
{
    return a*b%mod;
}
ll add(ll a,ll b)
{
    a+=b;
    if(a>=mod)
        a-=mod;
    return a;
}
ll sub(ll a,ll b)
{
    a-=b;
    if(a<0)
        a+=mod;
    return a;
}
int find(int tr)
{
    if(par[tr]==tr)
        return tr;
    return par[tr]=find(par[tr]);
}
void query(int a,int b,int t)
{
    int pa=p[a],pb=p[b];
    if(t==1)
        swap(p[a],p[b]);
    a=find(a);
    b=find(b);
    if(a==b)
        return;
    cnt[hsh[a]]-=siz[a];
    if(hsh[a]!=0)
        ans4-=(ll)siz[a]*cnt[sub(0,hsh[a])],ans3--;
    if(hsh[b]!=0)
        ans4-=(ll)siz[b]*cnt[sub(0,hsh[b])],ans3--;
    cnt[hsh[b]]-=siz[b];
    if(t==1)
    {
        hsh[a]=sub(hsh[a],pwr[pa]);
        hsh[a]=add(hsh[a],pwr[pb]);
        hsh[b]=sub(hsh[b],pwr[pb]);
        hsh[b]=add(hsh[b],pwr[pa]);
        if(hsh[b]!=0)
            cnt[hsh[b]]+=siz[b],ans4+=(ll)siz[b]*cnt[sub(0,hsh[b])],ans3++;
    }
    else
    {
        hsh[a]=add(hsh[a],hsh[b]);
        siz[a]+=siz[b];
        par[b]=a;
    }
    if(hsh[a]!=0)
        cnt[hsh[a]]+=siz[a],ans4+=(ll)siz[a]*cnt[sub(0,hsh[a])],ans3++;
}
int main()
{
	for(int i=0;i<N;i++)
        par[i]=i,pwr.pb(mul(pwr.back(),N));
    scanf("%i %i",&n,&qq);
    p.resize(n);
    for(int i=0;i<n;i++)
        scanf("%i",&p[i]);
    q=p;
    sort(q.begin(),q.end());
    for(int i=0;i<n;i++){
        hsh[i]=add(hsh[i],pwr[p[i]]),hsh[i]=sub(hsh[i],pwr[q[i]]),cnt[hsh[i]]++;
        if(hsh[i]!=0)
            ans4+=cnt[sub(0,hsh[i])],ans3++;
    }
    while(qq--)
    {
        int t,a,b;
        scanf("%i",&t);
        if(t==1||t==2)
            scanf("%i %i",&a,&b),query(a-1,b-1,t);
        if(t==3)
            printf(ans3==0?"DA\n":"NE\n");
        if(t==4)
            printf("%lld\n",ans4);
    }
    return 0;
}

Compilation message

zamjene.cpp: In function 'int main()':
zamjene.cpp:79:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i %i",&n,&qq);
     ~~~~~^~~~~~~~~~~~~~~~
zamjene.cpp:82:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i",&p[i]);
         ~~~~~^~~~~~~~~~~~
zamjene.cpp:93:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i",&t);
         ~~~~~^~~~~~~~~
zamjene.cpp:95:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%i %i",&a,&b),query(a-1,b-1,t);
             ~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 24288 KB Output is correct
2 Correct 35 ms 24288 KB Output is correct
3 Correct 35 ms 24288 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 24288 KB Output is correct
2 Correct 34 ms 24292 KB Output is correct
3 Correct 41 ms 24288 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 24288 KB Output is correct
2 Correct 35 ms 24288 KB Output is correct
3 Correct 35 ms 24348 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 24288 KB Output is correct
2 Correct 42 ms 24288 KB Output is correct
3 Correct 36 ms 24260 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 24288 KB Output is correct
2 Correct 35 ms 24288 KB Output is correct
3 Correct 35 ms 24260 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 24288 KB Output is correct
2 Correct 39 ms 24288 KB Output is correct
3 Correct 39 ms 24288 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 25148 KB Output is correct
2 Correct 92 ms 27992 KB Output is correct
3 Correct 109 ms 37168 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 646 ms 55124 KB Output is correct
2 Correct 1142 ms 182648 KB Output is correct
3 Correct 1414 ms 330956 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 924 ms 114576 KB Output is correct
2 Correct 1089 ms 112940 KB Output is correct
3 Correct 952 ms 113716 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 696 ms 41240 KB Output is correct
2 Correct 941 ms 114216 KB Output is correct
3 Correct 877 ms 113452 KB Output is correct