oj.uz

Submission #243785

# Submission time Handle Problem Language Result Execution time Memory
243785 2020-07-01T19:05:05 Z SamAnd I want to be the very best too! (NOI17_pokemonmaster) C++17
27 / 100
 5000 ms 305548 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;
    }
};

pban t[N * 4];

void ubd(int tl, int tr, int x, int y, bool z, int pos)
{
    if (!z)
        treap::han(t[pos], y);
    else
        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 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:253: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:263: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:307:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &b[x]);
         ~~~~~^~~~~~~~~~~~~
pokemonmaster.cpp:314:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &ty);
         ~~~~~^~~~~~~~~~~
pokemonmaster.cpp:318: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:327: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 738 ms 114776 KB Output is correct
2 Correct 1040 ms 115696 KB Output is correct
3 Correct 1418 ms 112368 KB Output is correct
4 Correct 811 ms 116464 KB Output is correct
5 Correct 1037 ms 115824 KB Output is correct
6 Correct 1374 ms 110696 KB Output is correct
7 Correct 542 ms 115952 KB Output is correct
8 Correct 943 ms 115824 KB Output is correct
9 Correct 642 ms 115952 KB Output is correct
10 Correct 1375 ms 111548 KB Output is correct
11 Correct 1094 ms 115696 KB Output is correct
12 Correct 1428 ms 101652 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 736 ms 114032 KB Output is correct
2 Correct 1002 ms 113904 KB Output is correct
3 Correct 1341 ms 109936 KB Output is correct
4 Correct 826 ms 114800 KB Output is correct
5 Correct 1046 ms 115184 KB Output is correct
6 Correct 1435 ms 107504 KB Output is correct
7 Correct 1223 ms 112880 KB Output is correct
8 Correct 1435 ms 112728 KB Output is correct
9 Correct 1197 ms 113112 KB Output is correct
10 Correct 1795 ms 102948 KB Output is correct
11 Correct 1500 ms 111832 KB Output is correct
12 Correct 1444 ms 93936 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1295 ms 130072 KB Output is correct
2 Correct 3613 ms 231920 KB Output is correct
3 Execution timed out 5098 ms 305548 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 738 ms 114776 KB Output is correct
2 Correct 1040 ms 115696 KB Output is correct
3 Correct 1418 ms 112368 KB Output is correct
4 Correct 811 ms 116464 KB Output is correct
5 Correct 1037 ms 115824 KB Output is correct
6 Correct 1374 ms 110696 KB Output is correct
7 Correct 542 ms 115952 KB Output is correct
8 Correct 943 ms 115824 KB Output is correct
9 Correct 642 ms 115952 KB Output is correct
10 Correct 1375 ms 111548 KB Output is correct
11 Correct 1094 ms 115696 KB Output is correct
12 Correct 1428 ms 101652 KB Output is correct
13 Correct 1500 ms 130652 KB Output is correct
14 Execution timed out 5080 ms 231204 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 738 ms 114776 KB Output is correct
2 Correct 1040 ms 115696 KB Output is correct
3 Correct 1418 ms 112368 KB Output is correct
4 Correct 811 ms 116464 KB Output is correct
5 Correct 1037 ms 115824 KB Output is correct
6 Correct 1374 ms 110696 KB Output is correct
7 Correct 542 ms 115952 KB Output is correct
8 Correct 943 ms 115824 KB Output is correct
9 Correct 642 ms 115952 KB Output is correct
10 Correct 1375 ms 111548 KB Output is correct
11 Correct 1094 ms 115696 KB Output is correct
12 Correct 1428 ms 101652 KB Output is correct
13 Correct 736 ms 114032 KB Output is correct
14 Correct 1002 ms 113904 KB Output is correct
15 Correct 1341 ms 109936 KB Output is correct
16 Correct 826 ms 114800 KB Output is correct
17 Correct 1046 ms 115184 KB Output is correct
18 Correct 1435 ms 107504 KB Output is correct
19 Correct 1223 ms 112880 KB Output is correct
20 Correct 1435 ms 112728 KB Output is correct
21 Correct 1197 ms 113112 KB Output is correct
22 Correct 1795 ms 102948 KB Output is correct
23 Correct 1500 ms 111832 KB Output is correct
24 Correct 1444 ms 93936 KB Output is correct
25 Correct 1295 ms 130072 KB Output is correct
26 Correct 3613 ms 231920 KB Output is correct
27 Execution timed out 5098 ms 305548 KB Time limit exceeded
28 Halted 0 ms 0 KB -