oj.uz

Submission #243782

# Submission time Handle Problem Language Result Execution time Memory
243782 2020-07-01T18:58:59 Z SamAnd I want to be the very best too! (NOI17_pokemonmaster) C++17
27 / 100
 5000 ms 289648 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 701 ms 114800 KB Output is correct
2 Correct 1047 ms 116464 KB Output is correct
3 Correct 1401 ms 113008 KB Output is correct
4 Correct 769 ms 117232 KB Output is correct
5 Correct 1004 ms 116316 KB Output is correct
6 Correct 1383 ms 111284 KB Output is correct
7 Correct 522 ms 116336 KB Output is correct
8 Correct 971 ms 116336 KB Output is correct
9 Correct 618 ms 116336 KB Output is correct
10 Correct 1389 ms 112204 KB Output is correct
11 Correct 1089 ms 116336 KB Output is correct
12 Correct 1385 ms 102200 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 746 ms 113904 KB Output is correct
2 Correct 978 ms 113776 KB Output is correct
3 Correct 1350 ms 109808 KB Output is correct
4 Correct 819 ms 114932 KB Output is correct
5 Correct 1050 ms 115184 KB Output is correct
6 Correct 1490 ms 107316 KB Output is correct
7 Correct 1206 ms 113776 KB Output is correct
8 Correct 1543 ms 113520 KB Output is correct
9 Correct 1240 ms 113820 KB Output is correct
10 Correct 1679 ms 103664 KB Output is correct
11 Correct 1611 ms 112476 KB Output is correct
12 Correct 1607 ms 94704 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1303 ms 129784 KB Output is correct
2 Correct 3612 ms 232432 KB Output is correct
3 Execution timed out 5088 ms 289648 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 701 ms 114800 KB Output is correct
2 Correct 1047 ms 116464 KB Output is correct
3 Correct 1401 ms 113008 KB Output is correct
4 Correct 769 ms 117232 KB Output is correct
5 Correct 1004 ms 116316 KB Output is correct
6 Correct 1383 ms 111284 KB Output is correct
7 Correct 522 ms 116336 KB Output is correct
8 Correct 971 ms 116336 KB Output is correct
9 Correct 618 ms 116336 KB Output is correct
10 Correct 1389 ms 112204 KB Output is correct
11 Correct 1089 ms 116336 KB Output is correct
12 Correct 1385 ms 102200 KB Output is correct
13 Correct 1561 ms 132468 KB Output is correct
14 Execution timed out 5021 ms 233432 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 701 ms 114800 KB Output is correct
2 Correct 1047 ms 116464 KB Output is correct
3 Correct 1401 ms 113008 KB Output is correct
4 Correct 769 ms 117232 KB Output is correct
5 Correct 1004 ms 116316 KB Output is correct
6 Correct 1383 ms 111284 KB Output is correct
7 Correct 522 ms 116336 KB Output is correct
8 Correct 971 ms 116336 KB Output is correct
9 Correct 618 ms 116336 KB Output is correct
10 Correct 1389 ms 112204 KB Output is correct
11 Correct 1089 ms 116336 KB Output is correct
12 Correct 1385 ms 102200 KB Output is correct
13 Correct 746 ms 113904 KB Output is correct
14 Correct 978 ms 113776 KB Output is correct
15 Correct 1350 ms 109808 KB Output is correct
16 Correct 819 ms 114932 KB Output is correct
17 Correct 1050 ms 115184 KB Output is correct
18 Correct 1490 ms 107316 KB Output is correct
19 Correct 1206 ms 113776 KB Output is correct
20 Correct 1543 ms 113520 KB Output is correct
21 Correct 1240 ms 113820 KB Output is correct
22 Correct 1679 ms 103664 KB Output is correct
23 Correct 1611 ms 112476 KB Output is correct
24 Correct 1607 ms 94704 KB Output is correct
25 Correct 1303 ms 129784 KB Output is correct
26 Correct 3612 ms 232432 KB Output is correct
27 Execution timed out 5088 ms 289648 KB Time limit exceeded
28 Halted 0 ms 0 KB -