Submission #166729

#	Time	Username	Problem	Language	Result	Execution time	Memory
166729		egekabas	Zamjene (COCI16_zamjene)	C++14	84 / 140	6070 ms	141276 KiB

zamjene

#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long   ll;
typedef unsigned long long   ull;
typedef long double ld;
typedef pair<ll, ll>    pll;
typedef pair<ull, ull>    pull;
typedef pair<ll, ll>  pii;
typedef pair<ld, ld>  pld;
ll plh[1000009];
ll valh[1000009];
ll prt[1000009];
ll sz[1000009];
ll mod = 1e9+7;
map<ll, ll> sfind;
ll n, q;
ll ar[1000009];
ll sr[1000009];
vector<ll> un;
ll pr = 0;

ll find(ll x){
    if(prt[x] == x)
        return x;
    return prt[x] = find(prt[x]);
}
void erase(ll x){
    ll tmp = (plh[x]-valh[x]+mod)%mod;
    ll tmp2 = mod-tmp;
    sfind[tmp] -= sz[x];
    if(tmp != 0)
        pr -= sz[x]*sfind[tmp2];
}
void add(ll y){
    ll tmp = (plh[y]-valh[y]+mod)%mod;
    ll tmp2 = mod-tmp;
    if(tmp != 0)
        pr += sz[y]*sfind[tmp2];
    sfind[tmp] += sz[y];
}
void merge(ll x, ll y){
    x = find(x);
    y = find(y);
    if(x == y)
        return;
    erase(x);
    erase(y);
    prt[x] = y;
    plh[y] =  (plh[y]+plh[x])%mod;
    valh[y] = (valh[y]+valh[x])%mod;
    sz[y] += sz[x];
    add(y);
}

ll pw(ll y){
    ll ret = 1;
    ll x = 31;
    ++y;
    while(y > 0){
        if(y%2)
            ret = ret*x%mod;
        x = x*x%mod;
        y /= 2;
    }
    return ret;
}
ll hashval(ll x){
    return pw(lower_bound(un.begin(), un.end(), x)-
    un.begin());
}
ll hashpl(ll x){
    return pw(lower_bound(un.begin(), un.end(), sr[x-1])-
    un.begin());
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    
    cin >> n >> q;
    for(ll i = 1; i <= n; ++i){
        cin >> ar[i];
        sr[i-1] = ar[i];
        
    }
    sort(sr, sr+n);
    for(int i = 0; i < n; ++i){
        if(un.size() > 0 && *(un.end()-1) == sr[i])
            continue;
        un.pb(sr[i]);
    }
    
    for(ll i = 1; i <= n; ++i){
        prt[i] = i;
        sz[i] = 1;
        plh[i] = hashpl(i);
        valh[i] = hashval(ar[i]);
        //cout << i << " " << hashpl(i) << " " << hashval(ar[i]) << "\n";
        add(i);
    }
    while(q--){
        ll t;
        cin >> t;
        if(t == 1){
            ll a, b;
            cin >> a >> b;
            ll a1 = find(a);
            ll b1 = find(b);
            erase(a1);
            erase(b1);
            valh[a1] -= hashval(ar[a]);
            valh[b1] -= hashval(ar[b]);
            
            valh[a1] += hashval(ar[b]);
            valh[b1] += hashval(ar[a]);
            
            valh[a1] %= mod;
            valh[b1] %= mod;

            if(valh[a1] < 0)
                valh[a1] += mod;
            if(valh[b1] < 0)
                valh[b1] += mod; 
            add(a1);
            add(b1);
            swap(ar[a], ar[b]);
        }
        if(t == 2){
            ll a, b;
            cin >> a >> b;
            merge(a, b);
        }
        if(t == 3){
            if(sfind[0] == n)
                cout << "DA\n";
            else
                cout << "NE\n";
        }
        if(t == 4){
            cout << pr << "\n";
        }
    }
}

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 0 / 14
• Subtask 8: 0 / 14
• Subtask 9: 0 / 14
• Subtask 10: 0 / 14