oj.uz

Submission #166731

# Submission time Handle Problem Language Result Execution time Memory
166731 2019-12-03T14:32:13 Z egekabas Zamjene (COCI16_zamjene) C++14
84 / 140
 6000 ms 59972 KB 
#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];
    if(sfind[tmp] == 0) 
        sfind.erase(tmp);
    if(sfind[tmp2] == 0) 
        sfind.erase(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];
    if(sfind[tmp] == 0) 
        sfind.erase(tmp);
    if(sfind[tmp2] == 0) 
        sfind.erase(tmp2);
}
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.0 / 14.0

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

Subtask #2
14.0 / 14.0

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

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 380 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 3 ms 376 KB Output is correct

Subtask #4
14.0 / 14.0

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

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 5 ms 508 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 916 KB Output is correct
2 Correct 15 ms 888 KB Output is correct
3 Correct 16 ms 1016 KB Output is correct

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 5400 KB Output is correct
2 Correct 200 ms 6056 KB Output is correct
3 Incorrect 338 ms 6836 KB Output isn't correct

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1882 ms 28772 KB Output is correct
2 Execution timed out 6090 ms 50496 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 3491 ms 59264 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1902 ms 52492 KB Output is correct
2 Incorrect 4342 ms 59972 KB Output isn't correct
3 Halted 0 ms 0 KB -