oj.uz

Submission #201660

# Submission time Handle Problem Language Result Execution time Memory
201660 2020-02-11T16:16:46 Z SamAnd Zamjene (COCI16_zamjene) C++17
126 / 140
 6000 ms 65632 KB 
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair

int ka()
{
    int x = 0;
    bool z = false;
    while (1)
    {
        char y = getchar();
        if ('0' <= y && y <= '9')
        {
            x = (x * 10) + (y - '0');
            z = true;
        }
        else
        {
            if (z)
                return x;
        }
    }
}

const int N = 1000006;
const int P = 1000003;
const int M = 1000000007;
const int P1 = 2000003;
const int M1 = 1000000009;
int ast[N], ast1[N];
void pre()
{
    ast[0] = 1;
    ast1[0] = 1;
    for (int i = 1; i < N; ++i)
    {
        ast[i] = (ast[i - 1] * 1LL * P) % M;
        ast1[i] = (ast1[i - 1] * 1LL * P1) % M1;
    }
}

int n, qqq;
int a[N], b[N];

map<pair<int, int>, int> mp;
long long ans4;

void ave(pair<int, int> x, int q)
{
    if (x.first || x.second)
    {
        ans4 += mp[m_p((M - x.first) % M, (M1 - x.second) % M1)] * 1LL * q;
        if (mp[m_p((M - x.first) % M, (M1 - x.second) % M1)] == 0)
            mp.erase(m_p((M - x.first) % M, (M1 - x.second) % M1));
    }
    mp[x] += q;
    if (mp[x] == 0)
        mp.erase(x);
}

void han(pair<int, int> x, int q)
{
    if (x.first || x.second)
    {
        ans4 -= mp[m_p((M - x.first) % M, (M1 - x.second) % M1)] * 1LL * q;
        if (mp[m_p((M - x.first) % M, (M1 - x.second) % M1)] == 0)
            mp.erase(m_p((M - x.first) % M, (M1 - x.second) % M1));
    }
    mp[x] -= q;
    if (mp[x] == 0)
        mp.erase(x);
}

int p[N];
int ha[N], hb[N];
int ha1[N], hb1[N];
int qq[N];

int fi(int x)
{
    if (x == p[x])
        return x;
    return p[x] = fi(p[x]);
}

pair<int, int> u(int x)
{
    return m_p((ha[x] - hb[x] + M) % M, (ha1[x] - hb1[x] + M1) % M1);
}

int main()
{
    //freopen("input.txt", "r", stdin);
    pre();
    n = ka();
    qqq = ka();
    for (int i = 1; i <= n; ++i)
    {
        a[i] = ka();
        b[i] = a[i];
    }
    sort(b + 1, b + n + 1);
    for (int i = 1; i <= n; ++i)
    {
        p[i] = i;
        ha[i] = ast[a[i]];
        hb[i] = ast[b[i]];
        ha1[i] = ast1[a[i]];
        hb1[i] = ast1[b[i]];
        qq[i] = 1;
        ave(u(i), qq[i]);
    }
    while (qqq--)
    {
        int ty;
        ty = ka();
        if (ty == 1)
        {
            int x, y;
            x = ka();
            y = ka();
            if (fi(x) == fi(y))
            {
                swap(a[x], a[y]);
                continue;
            }
            int xx = fi(x);
            int yy = fi(y);
            han(u(xx), qq[xx]);
            han(u(yy), qq[yy]);
            ha[xx] = (ha[xx] - ast[a[x]] + M) % M;
            ha[yy] = (ha[yy] - ast[a[y]] + M) % M;
            ha1[xx] = (ha1[xx] - ast1[a[x]] + M1) % M1;
            ha1[yy] = (ha1[yy] - ast1[a[y]] + M1) % M1;
            swap(a[x], a[y]);
            ha[xx] = (ha[xx] + ast[a[x]]) % M;
            ha[yy] = (ha[yy] + ast[a[y]]) % M;
            ha1[xx] = (ha1[xx] + ast1[a[x]]) % M1;
            ha1[yy] = (ha1[yy] + ast1[a[y]]) % M1;
            ave(u(xx), qq[xx]);
            ave(u(yy), qq[yy]);
        }
        else if (ty == 2)
        {
            int x, y;
            x = ka();
            y = ka();
            if (fi(x) == fi(y))
                continue;
            x = fi(x);
            y = fi(y);
            han(u(x), qq[x]);
            han(u(y), qq[y]);
            p[x] = y;
            ha[y] = (ha[y] + ha[x]) % M;
            hb[y] = (hb[y] + hb[x]) % M;
            ha1[y] = (ha1[y] + ha1[x]) % M1;
            hb1[y] = (hb1[y] + hb1[x]) % M1;
            qq[y] += qq[x];
            ave(u(y), qq[y]);
        }
        else if (ty == 3)
        {
            if (mp[m_p(0, 0)] == n)
                printf("DA\n");
            else
                printf("NE\n");
        }
        else
        {
            printf("%lld\n", ans4);
        }
    }
    return 0;
}

Subtask #1
14.0 / 14.0

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

Subtask #2
14.0 / 14.0

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

Subtask #3
14.0 / 14.0

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

Subtask #4
14.0 / 14.0

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

Subtask #5
14.0 / 14.0

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

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 8568 KB Output is correct
2 Correct 21 ms 8568 KB Output is correct
3 Correct 23 ms 8696 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 11768 KB Output is correct
2 Correct 148 ms 12408 KB Output is correct
3 Correct 233 ms 13048 KB Output is correct

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1467 ms 28692 KB Output is correct
2 Execution timed out 6053 ms 51008 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2825 ms 51348 KB Output is correct
2 Correct 5552 ms 65632 KB Output is correct
3 Correct 2422 ms 63284 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1344 ms 44720 KB Output is correct
2 Correct 3166 ms 52244 KB Output is correct
3 Correct 2464 ms 63356 KB Output is correct