oj.uz

답안 #243756

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
243756 2020-07-01T18:35:24 Z SamAnd I want to be the very best too! (NOI17_pokemonmaster) C++17
20 / 100
 354 ms 36592 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;
    if (it != s[i].end())
    {
        ubd(1, n * m, *it, x, false, 1);
        ubd(1, n * m, *it, hl, true, 1);
    }
    ubd(1, n * m, x, hl, false, 1);
    s[i].erase(x);
}

// for subtask 4
int t1[N * 4];

void ubd1(int tl, int tr, int x, int y, int pos)
{
    if (tl == tr)
    {
        t1[pos] = y;
        return;
    }
    int m = (tl + tr) / 2;
    if (x <= m)
        ubd1(tl, m, x, y, pos * 2);
    else
        ubd1(m + 1, tr, x, y, pos * 2 + 1);
    t1[pos] = t1[pos * 2] + t1[pos * 2 + 1];
}

int qry1(int tl, int tr, int l, int r, int pos)
{
    if (l > r)
        return 0;
    if (tl == l && tr == r)
        return t1[pos];
    int m = (tl + tr) / 2;
    return (qry1(tl, m, l, min(m, r), pos * 2) +
            qry1(m + 1, tr, max(m + 1, l), r, pos * 2 + 1));
}
//

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]);
        ubd1(1, n * m, tin[x], b[x] - 1, 1);
    }

    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]);
            ubd1(1, n * m, tin[x], p - 1, 1);
        }
        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 qq = qry1(1, n * m, tin[x], tout[x], 1);
            if (qq == 0 || qq == tout[x] - tin[x] + 1)
                printf("%d\n", 1);
            else
                printf("%d\n", 2);
        }
    }
}

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:283: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:293: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:337:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &b[x]);
         ~~~~~^~~~~~~~~~~~~
pokemonmaster.cpp:345:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &ty);
         ~~~~~^~~~~~~~~~~
pokemonmaster.cpp:349: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:359: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
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 167 ms 33492 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 171 ms 32624 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 301 ms 32960 KB Output is correct
2 Correct 275 ms 34904 KB Output is correct
3 Correct 240 ms 34544 KB Output is correct
4 Correct 268 ms 35952 KB Output is correct
5 Correct 291 ms 36336 KB Output is correct
6 Correct 354 ms 36592 KB Output is correct
7 Correct 278 ms 33772 KB Output is correct
8 Correct 280 ms 33780 KB Output is correct
9 Correct 328 ms 33776 KB Output is correct
10 Correct 273 ms 33776 KB Output is correct
11 Correct 281 ms 33772 KB Output is correct
12 Correct 274 ms 33776 KB Output is correct

Subtask #4
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 167 ms 33492 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 167 ms 33492 KB Output isn't correct
2 Halted 0 ms 0 KB -