oj.uz

Submission #243793

# Submission time Handle Problem Language Result Execution time Memory
243793 2020-07-01T19:16:59 Z SamAnd I want to be the very best too! (NOI17_pokemonmaster) C++17
47 / 100
 5000 ms 93040 KB 
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
typedef long long ll;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rnf(2106);
const int N = 50004;
const int xx[4] = {0, 1, 0, -1};
const int yy[4] = {1, 0, -1, 0};

int n, m, q;
int** a;

int p0[N];

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

void kpc(int x, int y)
{
    x = fi(x);
    y = fi(y);
    p0[x] = y;
}

int uu(int x, int y)
{
    return (x - 1) * m + y;
}

vector<int> g[N];

const int k = 18;
int p[N][k];

int tin[N], tout[N], ti;

void dfs0(int x, int p0)
{
    tin[x] = ++ti;
    p[x][0] = p0;
    for (int i = 1; i < k; ++i)
        p[x][i] = p[p[x][i - 1]][i - 1];
    for (int i = 0; i < g[x].size(); ++i)
    {
        int h = g[x][i];
        dfs0(h, x);
    }
    tout[x] = ti;
}

bool isp(int x, int y)
{
    return (tin[x] <= tin[y] && tout[y] <= tout[x]);
}

int go(int x, int y)
{
    for (int i = k - 1; i >= 0; --i)
    {
        int xx = p[x][i];
        int ux = (xx - 1) / m + 1;
        int uy = xx - (ux - 1) * m;
        if (a[ux][uy] <= y)
            x = xx;
    }
    return x;
}

int yyz;
int yyr[N * k * 5];
struct ban
{
    int x, y;
    ban *l, *r;
    int q;
    ban(){}
    ban(int x)
    {
        this->x = x;
        y = yyr[yyz++];
        l = r = 0;
        q = 1;
    }
};
typedef ban* pban;

namespace treap
{
    int getq(pban t)
    {
        if (t == 0)
            return 0;
        return t->q;
    }

    void ubd(pban t)
    {
        if (t == 0)
            return;
        t->q = getq(t->l) + 1 + getq(t->r);
    }

    void mer(pban l, pban r, pban& t)
    {
        if (l == 0)
        {
            t = r;
            return;
        }
        if (r == 0)
        {
            t = l;
            return;
        }
        if (l->y > r->y)
        {
            mer(l->r, r, l->r);
            t = l;
        }
        else
        {
            mer(l, r->l, r->l);
            t = r;
        }
        ubd(t);
    }

    void spl(pban t, int x, pban& l, pban& r)
    {
        if (t == 0)
        {
            l = r = 0;
            return;
        }
        if (x < t->x)
        {
            spl(t->l, x, l, t->l);
            r = t;
        }
        else
        {
            spl(t->r, x, t->r, r);
            l = t;
        }
        ubd(l);
        ubd(r);
    }

    void ave(pban& t, int x)
    {
        pban l, r;
        spl(t, x, l, r);
        pban m = new ban(x);
        mer(l, m, t);
        mer(t, r, t);
    }

    void han(pban& t, int x)
    {
        pban l, m, r;
        spl(t, x, m, r);
        spl(m, x - 1, l, m);
        mer(l, r, t);
    }

    int ph(pban& t, int x)
    {
        pban l, r;
        spl(t, x, l, r);
        int ans = getq(l);
        mer(l, r, t);
        return ans;
    }
};

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>
using namespace __gnu_pbds;
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;

ordered_set t[N * 4];

void ubd(int tl, int tr, int x, int y, bool z, int pos)
{
    if (!z)
    {
        t[pos].erase(y);
        //treap::han(t[pos], y);
    }
    else
    {
        t[pos].insert(y);
        //treap::ave(t[pos], y);
    }
    if (tl == tr)
        return;
    int m = (tl + tr) / 2;
    if (x <= m)
        ubd(tl, m, x, y, z, pos * 2);
    else
        ubd(m + 1, tr, x, y, z, pos * 2 + 1);
}

int qry(int tl, int tr, int l, int r, int x, int pos)
{
    if (l > r)
        return 0;
    if (tl == l && tr == r)
    {
        return t[pos].order_of_key(x + 1);
        //return treap::ph(t[pos], x);
    }
    int m = (tl + tr) / 2;
    return (qry(tl, m, l, min(m, r), x, pos * 2) +
            qry(m + 1, tr, max(m + 1, l), r, x, pos * 2 + 1));
}

set<int> s[N];

void ave(int i, int x)
{
    s[i].insert(x);
    auto it = s[i].find(x);
    --it;
    int hl = *it;
    ++it;
    ++it;
    if (it != s[i].end())
    {
        ubd(1, n * m, *it, hl, false, 1);
        ubd(1, n * m, *it, x, true, 1);
    }
    ubd(1, n * m, x, hl, true, 1);
}

void han(int i, int x)
{
    auto it = s[i].find(x);
    --it;
    int hl = *it;
    ++it;
    ++it;
    ubd(1, n * m, x, hl, false, 1);
    if (it != s[i].end())
    {
        ubd(1, n * m, *it, x, false, 1);
        ubd(1, n * m, *it, hl, true, 1);
    }
    s[i].erase(x);
}

int b[N];

void solv()
{
    scanf("%d%d%d", &n, &m, &q);
    a = new int*[n + 5];
    for (int i = 0; i < n + 5; ++i)
    {
        a[i] = new int[m + 5];
    }
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
        {
            scanf("%d", &a[i][j]);
        }
    }

    vector<pair<int, pair<int, int> > > v;
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
        {
            v.push_back(m_p(a[i][j], m_p(i, j)));
        }
    }
    sort(all(v));

    for (int i = 1; i <= n * m; ++i)
        p0[i] = i;
    for (int i = 0; i < n * m; ++i)
    {
        int x = v[i].se.fi;
        int y = v[i].se.se;
        for (int i = 0; i < 4; ++i)
        {
            int hx = x + xx[i];
            int hy = y + yy[i];
            if (!(hx >= 1 && hx <= n && hy >= 1 && hy <= m))
                continue;
            if (a[hx][hy] > a[x][y])
                continue;
            if (fi(uu(x, y)) != fi(uu(hx, hy)))
            {
                g[uu(x, y)].push_back(fi(uu(hx, hy)));
                kpc(uu(hx, hy), uu(x, y));
            }
        }
    }
    dfs0(uu(v.back().se.fi, v.back().se.se), uu(v.back().se.fi, v.back().se.se));

    for (int i = 1; i < N; ++i)
    {
        s[i].insert(-i);
    }

    for (int x = 1; x <= n * m; ++x)
    {
        scanf("%d", &b[x]);
        ave(b[x], tin[x]);
    }

    while (q--)
    {
        int ty;
        scanf("%d", &ty);
        if (ty == 1)
        {
            int x, y, p;
            scanf("%d%d%d", &y, &x, &p);
            x = uu(x, y);
            han(b[x], tin[x]);
            b[x] = p;
            ave(b[x], tin[x]);
        }
        else
        {
            int x, y, l;
            scanf("%d%d%d", &y, &x, &l);
            if (a[x][y] > l)
            {
                printf("0\n");
                continue;
            }
            x = uu(x, y);
            x = go(x, l);
            printf("%d\n", qry(1, n * m, tin[x], tout[x], tin[x] - 1, 1));
        }
    }
}

int main()
{
    #ifdef SOMETHING
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    #endif // SOMETHING
    //ios_base::sync_with_stdio(false), cin.tie(0);
    for (int i = 0; i < N * k * 5; ++i)
    {
        yyr[i] = i;
    }
    for (int i = N * k * 5 - 1; i >= 0; --i)
    {
        swap(yyr[i], yyr[rnd() % (i + 1)]);
    }
    solv();
    return 0;
}

//while ((double)clock() / CLOCKS_PER_SEC <= 0.9){}

Compilation message

pokemonmaster.cpp: In function 'void dfs0(int, int)':
pokemonmaster.cpp:52:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < g[x].size(); ++i)
                     ~~^~~~~~~~~~~~~
pokemonmaster.cpp: In function 'void solv()':
pokemonmaster.cpp:271:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &n, &m, &q);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
pokemonmaster.cpp:281:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &a[i][j]);
             ~~~~~^~~~~~~~~~~~~~~~
pokemonmaster.cpp:325:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &b[x]);
         ~~~~~^~~~~~~~~~~~~
pokemonmaster.cpp:332:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &ty);
         ~~~~~^~~~~~~~~~~
pokemonmaster.cpp:336:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d%d%d", &y, &x, &p);
             ~~~~~^~~~~~~~~~~~~~~~~~~~~~
pokemonmaster.cpp:345:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d%d%d", &y, &x, &l);
             ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 727 ms 90548 KB Output is correct
2 Correct 847 ms 90656 KB Output is correct
3 Correct 1126 ms 90608 KB Output is correct
4 Correct 757 ms 90608 KB Output is correct
5 Correct 831 ms 90608 KB Output is correct
6 Correct 1067 ms 90864 KB Output is correct
7 Correct 682 ms 90656 KB Output is correct
8 Correct 809 ms 90608 KB Output is correct
9 Correct 724 ms 90732 KB Output is correct
10 Correct 1160 ms 90608 KB Output is correct
11 Correct 913 ms 90824 KB Output is correct
12 Correct 1112 ms 90864 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 774 ms 90104 KB Output is correct
2 Correct 868 ms 90352 KB Output is correct
3 Correct 1106 ms 90068 KB Output is correct
4 Correct 780 ms 91300 KB Output is correct
5 Correct 908 ms 91504 KB Output is correct
6 Correct 1198 ms 90208 KB Output is correct
7 Correct 903 ms 89072 KB Output is correct
8 Correct 1089 ms 89248 KB Output is correct
9 Correct 921 ms 89072 KB Output is correct
10 Correct 1320 ms 89200 KB Output is correct
11 Correct 1144 ms 89072 KB Output is correct
12 Correct 1163 ms 88952 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1292 ms 91376 KB Output is correct
2 Correct 2431 ms 91248 KB Output is correct
3 Correct 3203 ms 91120 KB Output is correct
4 Correct 3286 ms 92824 KB Output is correct
5 Correct 2541 ms 93040 KB Output is correct
6 Correct 1416 ms 91632 KB Output is correct
7 Correct 2633 ms 90352 KB Output is correct
8 Correct 2638 ms 90348 KB Output is correct
9 Correct 2588 ms 90480 KB Output is correct
10 Correct 2451 ms 90608 KB Output is correct
11 Correct 2492 ms 90784 KB Output is correct
12 Correct 2495 ms 90664 KB Output is correct

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 727 ms 90548 KB Output is correct
2 Correct 847 ms 90656 KB Output is correct
3 Correct 1126 ms 90608 KB Output is correct
4 Correct 757 ms 90608 KB Output is correct
5 Correct 831 ms 90608 KB Output is correct
6 Correct 1067 ms 90864 KB Output is correct
7 Correct 682 ms 90656 KB Output is correct
8 Correct 809 ms 90608 KB Output is correct
9 Correct 724 ms 90732 KB Output is correct
10 Correct 1160 ms 90608 KB Output is correct
11 Correct 913 ms 90824 KB Output is correct
12 Correct 1112 ms 90864 KB Output is correct
13 Correct 1203 ms 91376 KB Output is correct
14 Correct 3127 ms 91368 KB Output is correct
15 Execution timed out 5067 ms 92648 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 727 ms 90548 KB Output is correct
2 Correct 847 ms 90656 KB Output is correct
3 Correct 1126 ms 90608 KB Output is correct
4 Correct 757 ms 90608 KB Output is correct
5 Correct 831 ms 90608 KB Output is correct
6 Correct 1067 ms 90864 KB Output is correct
7 Correct 682 ms 90656 KB Output is correct
8 Correct 809 ms 90608 KB Output is correct
9 Correct 724 ms 90732 KB Output is correct
10 Correct 1160 ms 90608 KB Output is correct
11 Correct 913 ms 90824 KB Output is correct
12 Correct 1112 ms 90864 KB Output is correct
13 Correct 774 ms 90104 KB Output is correct
14 Correct 868 ms 90352 KB Output is correct
15 Correct 1106 ms 90068 KB Output is correct
16 Correct 780 ms 91300 KB Output is correct
17 Correct 908 ms 91504 KB Output is correct
18 Correct 1198 ms 90208 KB Output is correct
19 Correct 903 ms 89072 KB Output is correct
20 Correct 1089 ms 89248 KB Output is correct
21 Correct 921 ms 89072 KB Output is correct
22 Correct 1320 ms 89200 KB Output is correct
23 Correct 1144 ms 89072 KB Output is correct
24 Correct 1163 ms 88952 KB Output is correct
25 Correct 1292 ms 91376 KB Output is correct
26 Correct 2431 ms 91248 KB Output is correct
27 Correct 3203 ms 91120 KB Output is correct
28 Correct 3286 ms 92824 KB Output is correct
29 Correct 2541 ms 93040 KB Output is correct
30 Correct 1416 ms 91632 KB Output is correct
31 Correct 2633 ms 90352 KB Output is correct
32 Correct 2638 ms 90348 KB Output is correct
33 Correct 2588 ms 90480 KB Output is correct
34 Correct 2451 ms 90608 KB Output is correct
35 Correct 2492 ms 90784 KB Output is correct
36 Correct 2495 ms 90664 KB Output is correct
37 Correct 1203 ms 91376 KB Output is correct
38 Correct 3127 ms 91368 KB Output is correct
39 Execution timed out 5067 ms 92648 KB Time limit exceeded
40 Halted 0 ms 0 KB -