oj.uz

Submission #96788

# Submission time Handle Problem Language Result Execution time Memory
96788 2019-02-12T02:30:54 Z tieunhi Zamjene (COCI16_zamjene) C++11
140 / 140
 5456 ms 181804 KB 
#include <bits/stdc++.h>
#define FOR(i, u, v) for (int i = u; i <= v; i++)
#define FORD(i, v, u) for (int i = v; i >= u; i--)
#define ll long long
#define pill pair<int, ll>
#define PB push_back
#define mp make_pair
#define F first
#define S second
#define N 1000005
#define BASE 97
#define maxc 1000000007
#define mid (r + l)/2

using namespace std;

int n, numQ, a[N], b[N], sz[N], numCC, cc, root[N];
ll val[2][N], ansType4, base[N];
map<ll, int> ma;

template <typename T> inline void read(T &x){char c;bool nega=0;while((!isdigit(c=getchar()))&&(c!='-'));if(c=='-'){nega=1;c=getchar();}x=c-48;while(isdigit(c=getchar())) x=x*10+c-48;if(nega) x=-x;}
template <typename T> inline void writep(T x){if(x>9) writep(x/10);putchar(x%10+48);}
template <typename T> inline void write(T x){if(x<0){putchar('-');x=-x;}writep(x);putchar(' ');}
template <typename T> inline void writeln(T x){write(x);putchar('\n');}

void setup()
{
    read(n); read(numQ); cc = n;
    FOR(i, 1, n) read(a[i]), b[i] = a[i];
}
void subcc(int u)
{
    ll Val = val[0][u] - val[1][u];
    if (Val == 0)
    {
        numCC--;
        return;
    }
    ansType4 -= 1ll*sz[u]*ma[-Val];
    ma[Val] -= sz[u];
}
void addcc(int u)
{
    ll Val = val[0][u] - val[1][u];
    if (Val == 0)
    {
        numCC++;
        return;
    }
    ansType4 += 1ll*sz[u]*ma[-Val];
    ma[Val] += sz[u];

}
void prepare()
{
    sort(b+1, b+n+1);
    base[0] = 1;
    FOR(i, 1, N-1) base[i] = base[i-1]*BASE;
    FOR(i, 1, n)
    {
        sz[i] = 1;
        val[0][i] = base[a[i]];
        val[1][i] = base[b[i]];
        addcc(i);
    }
}
int get_root(int u)
{
    return (root[u] == 0) ? u : root[u] = get_root(root[u]);
}
void inline add(ll &A, ll B) {A += B;}
void inline sub(ll &A, ll B) {A -= B;}

int main()
{
    ios_base::sync_with_stdio(0); cout.tie(0);
    //freopen("INP.TXT", "r", stdin);
    //freopen("OUT.TXT", "w", stdout);
    setup();
    prepare();
    while (numQ--)
    {
        int type, u, v; read(type);
        if (type <= 2) read(u), read(v);
        if (type == 1)
        {
            int p = get_root(u);
            int q = get_root(v);
            if (p == q)
            {
                swap(a[u], a[v]);
                continue;
            }

            subcc(p); subcc(q);
            add(val[0][p], base[a[v]]);
            add(val[0][q], base[a[u]]);
            sub(val[0][p], base[a[u]]);
            sub(val[0][q], base[a[v]]);
            swap(a[u], a[v]);
            addcc(p); addcc(q);
        }
        else if (type == 2)
        {
            int p = get_root(u);
            int q = get_root(v);
            if (p == q) continue;

            subcc(p); subcc(q);
            root[q] = p; sz[p] += sz[q];
            add(val[0][p], val[0][q]);
            add(val[1][p], val[1][q]);
            cc--;
            addcc(p);
        }
        else if (type == 3)
        {
            if (cc == numCC) cout <<"DA\n";
            else cout <<"NE\n";
        }
        else cout <<ansType4<<'\n';
    }
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8184 KB Output is correct
2 Correct 7 ms 8184 KB Output is correct
3 Correct 7 ms 8056 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8188 KB Output is correct
2 Correct 8 ms 8184 KB Output is correct
3 Correct 8 ms 8056 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8184 KB Output is correct
2 Correct 8 ms 8316 KB Output is correct
3 Correct 9 ms 8312 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8184 KB Output is correct
2 Correct 8 ms 8312 KB Output is correct
3 Correct 10 ms 8336 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8184 KB Output is correct
2 Correct 8 ms 8312 KB Output is correct
3 Correct 9 ms 8312 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 8696 KB Output is correct
2 Correct 12 ms 8696 KB Output is correct
3 Correct 11 ms 8824 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 11768 KB Output is correct
2 Correct 92 ms 13652 KB Output is correct
3 Correct 151 ms 16764 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1093 ms 40276 KB Output is correct
2 Correct 5072 ms 131080 KB Output is correct
3 Correct 5456 ms 181804 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2109 ms 81236 KB Output is correct
2 Correct 4091 ms 102264 KB Output is correct
3 Correct 1529 ms 89976 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 848 ms 47044 KB Output is correct
2 Correct 3032 ms 86264 KB Output is correct
3 Correct 1589 ms 90100 KB Output is correct