oj.uz

Submission #243798

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

int nz;
int ul[N * k * k * 3], ur[N * k * k * 3];
int ss[N * k * k * 3];
namespace nosr
{
    void ubd(int tl, int tr, int x, int y, int pos)
    {
        ss[pos] += y;
        if (tl == tr)
        {
            return;
        }
        int m = (tl + tr) / 2;
        if (x <= m)
        {
            if (!ul[pos])
                ul[pos] = ++nz;
            ubd(tl, m, x, y, ul[pos]);
        }
        else
        {
            if (!ur[pos])
                ur[pos] = ++nz;
            ubd(m + 1, tr, x, y, ur[pos]);
        }
    }
    int qry(int tl, int tr, int l, int r, int pos)
    {
        if (l > r)
            return 0;
        if (!ss[pos])
            return 0;
        if (tl == l && tr == r)
            return ss[pos];
        int m = (tl + tr) / 2;
        return (qry(tl, m, l, min(m, r), ul[pos]) +
                qry(m + 1, tr, max(m + 1, l), r, ur[pos]));
    }
};


int t[N * 4];

void ubd(int tl, int tr, int x, int y, bool z, int pos)
{
    if (!z)
    {
        if (!t[pos])
            t[pos] = ++nz;
        nosr::ubd(0, n * m, y, -1, t[pos]);
        //treap::han(t[pos], y);
    }
    else
    {
        if (!t[pos])
            t[pos] = ++nz;
        nosr::ubd(0, n * m, y, 1, t[pos]);
        //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 nosr::qry(0, n * m, 0, x, t[pos]);
        //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(0);
        //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:305: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:315: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:360:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &b[x]);
         ~~~~~^~~~~~~~~~~~~
pokemonmaster.cpp:367:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &ty);
         ~~~~~^~~~~~~~~~~
pokemonmaster.cpp:371: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:380: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 349 ms 92912 KB Output is correct
2 Correct 386 ms 104560 KB Output is correct
3 Correct 474 ms 122352 KB Output is correct
4 Correct 355 ms 93040 KB Output is correct
5 Correct 387 ms 103536 KB Output is correct
6 Correct 450 ms 120176 KB Output is correct
7 Correct 347 ms 90864 KB Output is correct
8 Correct 380 ms 100208 KB Output is correct
9 Correct 348 ms 92016 KB Output is correct
10 Correct 458 ms 121200 KB Output is correct
11 Correct 398 ms 108276 KB Output is correct
12 Correct 418 ms 109936 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 348 ms 91760 KB Output is correct
2 Correct 379 ms 103152 KB Output is correct
3 Correct 472 ms 119408 KB Output is correct
4 Correct 376 ms 94192 KB Output is correct
5 Correct 453 ms 114416 KB Output is correct
6 Correct 597 ms 138864 KB Output is correct
7 Correct 498 ms 78064 KB Output is correct
8 Correct 701 ms 107948 KB Output is correct
9 Correct 504 ms 82800 KB Output is correct
10 Correct 888 ms 143852 KB Output is correct
11 Correct 781 ms 126444 KB Output is correct
12 Correct 557 ms 119664 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 763 ms 91132 KB Output is correct
2 Correct 1238 ms 94704 KB Output is correct
3 Correct 1447 ms 96188 KB Output is correct
4 Correct 1651 ms 97612 KB Output is correct
5 Correct 1296 ms 95892 KB Output is correct
6 Correct 876 ms 91120 KB Output is correct
7 Correct 1438 ms 85104 KB Output is correct
8 Correct 1477 ms 85052 KB Output is correct
9 Correct 1391 ms 85104 KB Output is correct
10 Correct 1429 ms 85228 KB Output is correct
11 Correct 1399 ms 85100 KB Output is correct
12 Correct 1378 ms 84976 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 349 ms 92912 KB Output is correct
2 Correct 386 ms 104560 KB Output is correct
3 Correct 474 ms 122352 KB Output is correct
4 Correct 355 ms 93040 KB Output is correct
5 Correct 387 ms 103536 KB Output is correct
6 Correct 450 ms 120176 KB Output is correct
7 Correct 347 ms 90864 KB Output is correct
8 Correct 380 ms 100208 KB Output is correct
9 Correct 348 ms 92016 KB Output is correct
10 Correct 458 ms 121200 KB Output is correct
11 Correct 398 ms 108276 KB Output is correct
12 Correct 418 ms 109936 KB Output is correct
13 Correct 805 ms 95476 KB Output is correct
14 Correct 2124 ms 158960 KB Output is correct
15 Correct 3661 ms 302740 KB Output is correct
16 Correct 1632 ms 112132 KB Output is correct
17 Correct 1975 ms 155276 KB Output is correct
18 Correct 1135 ms 141040 KB Output is correct
19 Correct 1136 ms 94068 KB Output is correct
20 Correct 1764 ms 140712 KB Output is correct
21 Correct 1220 ms 100908 KB Output is correct
22 Correct 2591 ms 238832 KB Output is correct
23 Correct 2273 ms 176880 KB Output is correct
24 Correct 2039 ms 206928 KB Output is correct

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 349 ms 92912 KB Output is correct
2 Correct 386 ms 104560 KB Output is correct
3 Correct 474 ms 122352 KB Output is correct
4 Correct 355 ms 93040 KB Output is correct
5 Correct 387 ms 103536 KB Output is correct
6 Correct 450 ms 120176 KB Output is correct
7 Correct 347 ms 90864 KB Output is correct
8 Correct 380 ms 100208 KB Output is correct
9 Correct 348 ms 92016 KB Output is correct
10 Correct 458 ms 121200 KB Output is correct
11 Correct 398 ms 108276 KB Output is correct
12 Correct 418 ms 109936 KB Output is correct
13 Correct 348 ms 91760 KB Output is correct
14 Correct 379 ms 103152 KB Output is correct
15 Correct 472 ms 119408 KB Output is correct
16 Correct 376 ms 94192 KB Output is correct
17 Correct 453 ms 114416 KB Output is correct
18 Correct 597 ms 138864 KB Output is correct
19 Correct 498 ms 78064 KB Output is correct
20 Correct 701 ms 107948 KB Output is correct
21 Correct 504 ms 82800 KB Output is correct
22 Correct 888 ms 143852 KB Output is correct
23 Correct 781 ms 126444 KB Output is correct
24 Correct 557 ms 119664 KB Output is correct
25 Correct 763 ms 91132 KB Output is correct
26 Correct 1238 ms 94704 KB Output is correct
27 Correct 1447 ms 96188 KB Output is correct
28 Correct 1651 ms 97612 KB Output is correct
29 Correct 1296 ms 95892 KB Output is correct
30 Correct 876 ms 91120 KB Output is correct
31 Correct 1438 ms 85104 KB Output is correct
32 Correct 1477 ms 85052 KB Output is correct
33 Correct 1391 ms 85104 KB Output is correct
34 Correct 1429 ms 85228 KB Output is correct
35 Correct 1399 ms 85100 KB Output is correct
36 Correct 1378 ms 84976 KB Output is correct
37 Correct 805 ms 95476 KB Output is correct
38 Correct 2124 ms 158960 KB Output is correct
39 Correct 3661 ms 302740 KB Output is correct
40 Correct 1632 ms 112132 KB Output is correct
41 Correct 1975 ms 155276 KB Output is correct
42 Correct 1135 ms 141040 KB Output is correct
43 Correct 1136 ms 94068 KB Output is correct
44 Correct 1764 ms 140712 KB Output is correct
45 Correct 1220 ms 100908 KB Output is correct
46 Correct 2591 ms 238832 KB Output is correct
47 Correct 2273 ms 176880 KB Output is correct
48 Correct 2039 ms 206928 KB Output is correct
49 Correct 815 ms 96368 KB Output is correct
50 Correct 2053 ms 160368 KB Output is correct
51 Correct 3756 ms 304068 KB Output is correct
52 Correct 1836 ms 113936 KB Output is correct
53 Correct 2242 ms 167792 KB Output is correct
54 Correct 1484 ms 159732 KB Output is correct
55 Correct 1334 ms 81136 KB Output is correct
56 Correct 2343 ms 144764 KB Output is correct
57 Correct 1426 ms 90864 KB Output is correct
58 Correct 3138 ms 258332 KB Output is correct
59 Correct 3040 ms 190612 KB Output is correct
60 Correct 2336 ms 213716 KB Output is correct