oj.uz

Submission #201592

# Submission time Handle Problem Language Result Execution time Memory
201592 2020-02-11T10:24:34 Z SamAnd Zamjene (COCI16_zamjene) C++17
0 / 140
 2735 ms 71712 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 1000006;
const int P = 1000003;
const int M = 1000000007;
int ast[N];
void pre()
{
    ast[0] = 1;
    for (int i = 1; i < N; ++i)
        ast[i] = (ast[i - 1] * 1LL * P) % M;
}

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

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

void ave(int x, int q)
{
    mp[x] += q;
    if (x)
    {
        ans4 += mp[(M - x) % M] * 1LL * q;
    }
}

void han(int x, int q)
{
    mp[x] -= q;
    if (x)
    {
        ans4 -= mp[(M - x) % M] * 1LL * q;
    }
}

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

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

int main()
{
    pre();
    scanf("%d%d", &n, &qqq);
    for (int i = 1; i <= n; ++i)
    {
        scanf("%d", &a[i]);
        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]];
        qq[i] = 1;
        ave((ha[i] - hb[i] + M) % M, qq[i]);
    }
    while (qqq--)
    {
        int ty;
        scanf("%d", &ty);
        if (ty == 1)
        {
            int x, y;
            scanf("%d%d", &x, &y);
            if (fi(x) == fi(y))
                continue;
            int xx = fi(x);
            int yy = fi(y);
            han((ha[xx] - hb[xx] + M) % M, qq[xx]);
            han((ha[yy] - hb[yy] + M) % M, qq[yy]);
            ha[xx] = (ha[xx] - ast[a[x]] + M) % M;
            ha[yy] = (ha[yy] - ast[a[y]] + M) % M;
            swap(a[x], a[y]);
            ha[xx] = (ha[xx] + ast[a[x]]) % M;
            ha[yy] = (ha[yy] + ast[a[y]]) % M;
            ave((ha[xx] - hb[xx] + M) % M, qq[xx]);
            ave((ha[yy] - hb[yy] + M) % M, qq[yy]);
        }
        else if (ty == 2)
        {
            int x, y;
            scanf("%d%d", &x, &y);
            if (fi(x) == fi(y))
                continue;
            x = fi(x);
            y = fi(y);
            han((ha[x] - hb[x] + M) % M, qq[x]);
            han((ha[y] - hb[y] + M) % M, qq[y]);
            p[x] = y;
            ha[y] += ha[x];
            hb[y] += hb[x];
            qq[y] += qq[x];
            ave((ha[y] - hb[y] + M) % M, qq[y]);
        }
        else if (ty == 3)
        {
            if (mp[0] == n)
                printf("DA\n");
            else
                printf("NE\n");
        }
        else
        {
            printf("%lld\n", ans4);
        }
    }
    return 0;
}

Compilation message

zamjene.cpp: In function 'int main()':
zamjene.cpp:52:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &qqq);
     ~~~~~^~~~~~~~~~~~~~~~~~
zamjene.cpp:55:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &a[i]);
         ~~~~~^~~~~~~~~~~~~
zamjene.cpp:70:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &ty);
         ~~~~~^~~~~~~~~~~
zamjene.cpp:74:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d%d", &x, &y);
             ~~~~~^~~~~~~~~~~~~~~~
zamjene.cpp:92:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d%d", &x, &y);
             ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 14.0

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

Subtask #2
0 / 14.0

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

Subtask #3
0 / 14.0

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

Subtask #4
0 / 14.0

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

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 4344 KB Output is correct
2 Incorrect 13 ms 4344 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 14.0

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

Subtask #7
0 / 14.0

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

Subtask #8
0 / 14.0

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

Subtask #9
0 / 14.0

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

Subtask #10
0 / 14.0

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