oj.uz

Submission #132364

# Submission time Handle Problem Language Result Execution time Memory
132364 2019-07-18T18:33:53 Z nikolapesic2802 Zamjene (COCI16_zamjene) C++14
140 / 140
 2432 ms 470812 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>

#define ll long long
#define pb push_back
#define sz(x) (int)(x).size()
#define mp make_pair
#define f first
#define s second
#define all(x) x.begin(), x.end()
#define D(x) cerr << #x << " is " << (x) << "\n";

using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>; ///find_by_order(),order_of_key()
template<class T1, class T2> ostream& operator<<(ostream& os, const pair<T1,T2>& a) { os << '{' << a.f << ", " << a.s << '}'; return os; }
template<class T> ostream& operator<<(ostream& os, const vector<T>& a){os << '{';for(int i=0;i<sz(a);i++){if(i>0&&i<sz(a))os << ", ";os << a[i];}os<<'}';return os;}
template<class T> ostream& operator<<(ostream& os, const set<T>& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;}
template<class T> ostream& operator<<(ostream& os, const multiset<T>& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;}
template<class T1,class T2> ostream& operator<<(ostream& os, const map<T1,T2>& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;}

gp_hash_table<ll,int> cnt;
const int m=1e6+1,N=1e6+1;
const ll mod=9223362813479;
vector<int> par(N),p,q;
vector<ll> pwr,hsh(N);
vector<multiset<int> > imam(N),treba(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 merge(int a,int b)
{
    a=find(a);
    b=find(b);
    if(a==b)
        return;
    cnt[hsh[a]]-=imam[a].size();
    if(hsh[a]!=0)
        ans4-=(ll)2*imam[a].size()*cnt[sub(0,hsh[a])],ans3--;
    if(hsh[b]!=0)
        ans4-=(ll)2*imam[b].size()*cnt[sub(0,hsh[b])],ans3--;
    cnt[hsh[b]]-=imam[b].size();
    if(imam[a].size()<imam[b].size())
        swap(a,b);
    for(auto d:imam[b])
        hsh[a]=add(hsh[a],pwr[d]),imam[a].insert(d);
    for(auto d:treba[b])
        hsh[a]=sub(hsh[a],pwr[d]),treba[a].insert(d);
    imam[b].clear();
    treba[b].clear();
    par[b]=a;
    if(hsh[a]!=0)
        cnt[hsh[a]]+=imam[a].size(),ans4+=(ll)2*imam[a].size()*cnt[sub(0,hsh[a])],ans3++;
}
void swapuj(int a,int b)
{
    int pa=p[a],pb=p[b];
    swap(p[a],p[b]);
    a=find(a);
    b=find(b);
    if(a==b)
        return;
    cnt[hsh[a]]-=imam[a].size();
    if(hsh[a]!=0)
        ans4-=(ll)2*imam[a].size()*cnt[sub(0,hsh[a])],ans3--;
    if(hsh[b]!=0)
        ans4-=(ll)2*imam[b].size()*cnt[sub(0,hsh[b])],ans3--;
    cnt[hsh[b]]-=imam[b].size();
    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]);
    imam[a].erase(imam[a].find(pa));
    imam[a].insert(pb);
    imam[b].erase(imam[b].find(pb));
    imam[b].insert(pa);
    cnt[hsh[a]]+=imam[a].size();
    if(hsh[a]!=0)
        ans4+=(ll)2*imam[a].size()*cnt[sub(0,hsh[a])],ans3++;
    cnt[hsh[b]]+=imam[b].size();
    if(hsh[b]!=0)
        ans4+=(ll)2*imam[b].size()*cnt[sub(0,hsh[b])],ans3++;
}
int main()
{
    //freopen("in.txt","r",stdin);
    pwr.pb(1);
	for(int i=0;i<N;i++)
        par[i]=i,pwr.pb(mul(pwr.back(),m));
    scanf("%i %i",&n,&qq);
    p.resize(n);
    for(int i=0;i<n;i++)
        scanf("%i",&p[i]);
    q=p;
    sort(all(q));
    for(int i=0;i<n;i++)
        imam[i].insert(p[i]),hsh[i]=add(hsh[i],pwr[p[i]]),treba[i].insert(q[i]),hsh[i]=sub(hsh[i],pwr[q[i]]),cnt[hsh[i]]++;
    for(int i=0;i<n;i++)
        if(hsh[i]!=0)
            ans4+=cnt[sub(0,hsh[i])],ans3++;
    while(qq--)
    {
        int t,a,b;
        scanf("%i",&t);
        if(t==1)
            scanf("%i %i",&a,&b),swapuj(a-1,b-1);
        if(t==2)
            scanf("%i %i",&a,&b),merge(a-1,b-1);
        if(t==3)
            printf(ans3==0?"DA\n":"NE\n");
        if(t==4)
            printf("%lld\n",ans4/2);
    }
    return 0;
}

Compilation message

zamjene.cpp: In function 'int main()':
zamjene.cpp:119: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:122:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i",&p[i]);
         ~~~~~^~~~~~~~~~~~
zamjene.cpp:133:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i",&t);
         ~~~~~^~~~~~~~~
zamjene.cpp:135:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%i %i",&a,&b),swapuj(a-1,b-1);
             ~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
zamjene.cpp:137:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%i %i",&a,&b),merge(a-1,b-1);
             ~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 114400 KB Output is correct
2 Correct 118 ms 114400 KB Output is correct
3 Correct 117 ms 114276 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 114400 KB Output is correct
2 Correct 129 ms 114532 KB Output is correct
3 Correct 122 ms 114296 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 114440 KB Output is correct
2 Correct 118 ms 114404 KB Output is correct
3 Correct 118 ms 114384 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 114356 KB Output is correct
2 Correct 122 ms 114448 KB Output is correct
3 Correct 122 ms 114360 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 114316 KB Output is correct
2 Correct 119 ms 114296 KB Output is correct
3 Correct 119 ms 114400 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 115136 KB Output is correct
2 Correct 125 ms 115296 KB Output is correct
3 Correct 133 ms 115360 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 232 ms 124628 KB Output is correct
2 Correct 279 ms 128004 KB Output is correct
3 Correct 257 ms 136532 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1655 ms 192460 KB Output is correct
2 Correct 2049 ms 314360 KB Output is correct
3 Correct 2432 ms 470812 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1845 ms 299296 KB Output is correct
2 Correct 1988 ms 298736 KB Output is correct
3 Correct 1754 ms 308988 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1602 ms 226252 KB Output is correct
2 Correct 1839 ms 298564 KB Output is correct
3 Correct 1779 ms 309068 KB Output is correct