oj.uz

Submission #404045

# Submission time Handle Problem Language Result Execution time Memory
404045 2021-05-13T17:19:32 Z SamAnd Comparing Plants (IOI20_plants) C++17
44 / 100
 603 ms 17276 KB 
#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define m_p make_pair
#define fi first
#define se second
const int N = 200005;

int n, k;
vector<int> r;

pair<int, int> t[N * 4];
int laz[N * 4];
void shi(int pos)
{
    t[pos * 2].fi += laz[pos];
    laz[pos * 2] += laz[pos];
    t[pos * 2 + 1].fi += laz[pos];
    laz[pos * 2 + 1] += laz[pos];
    laz[pos] = 0;
}

void bil(int tl, int tr, int pos)
{
    if (tl == tr)
    {
        t[pos] = m_p(r[tl], tl);
        return;
    }
    int m = (tl + tr) / 2;
    bil(tl, m, pos * 2);
    bil(m + 1, tr, pos * 2 + 1);
    t[pos] = min(t[pos * 2], t[pos * 2 + 1]);
}

void ubd(int tl, int tr, int l, int r, int y, int pos)
{
    if (l > r)
        return;
    if (tl == l && tr == r)
    {
        t[pos].fi += y;
        laz[pos] += y;
        return;
    }
    shi(pos);
    int m = (tl + tr) / 2;
    ubd(tl, m, l, min(m, r), y, pos * 2);
    ubd(m + 1, tr, max(m + 1, l), r, y, pos * 2 + 1);
    t[pos] = min(t[pos * 2], t[pos * 2 + 1]);
}

pair<int, int> qry(int tl, int tr, int l, int r, int pos)
{
    if (l > r)
        return m_p(N, 0);
    if (tl == l && tr == r)
        return t[pos];
    shi(pos);
    int m = (tl + tr) / 2;
    return min(qry(tl, m, l, min(m, r), pos * 2),
               qry(m + 1, tr, max(m + 1, l), r, pos * 2 + 1));
}

vector<int> ans;
void rec(int i)
{
    while (1)
    {
        pair<int, int> u = m_p(N, 0);
        if (i - k + 1 >= 0)
        {
            u = min(u, qry(0, n - 1, i - k + 1, i - 1, 1));
        }
        else
        {
            u = min(u, qry(0, n - 1, 0, i - 1, 1));
            u = min(u, qry(0, n - 1, n + (i - k + 1), n - 1, 1));
        }
        if (u.fi)
            break;
        rec(u.se);
    }
    ans.push_back(i);
    if (i - k + 1 >= 0)
    {
        ubd(0, n - 1, i - k + 1, i - 1, -1, 1);
    }
    else
    {
        ubd(0, n - 1, 0, i - 1, -1, 1);
        ubd(0, n - 1, n + (i - k + 1), n - 1, -1, 1);
    }
    ubd(0, n - 1, i, i, N, 1);
}

vector<int> u;
void init(int k, vector<int> r)
{
    n = sz(r);
    ::k = k;
    ::r = r;

    bil(0, n - 1, 1);

    while (sz(ans) != n)
    {
        rec(t[1].se);
    }

    for (int i = 0; i < n; ++i)
        u.push_back(0);
    for (int i = 0; i < n; ++i)
        u[ans[i]] = i;
}

int compare_plants(int x, int y)
{
    if (u[x] < u[y])
        return 1;
    return -1;
}

/*
5 5 4
4 3 2 1 0
0 1
1 2
2 3
3 4
*/

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Incorrect 1 ms 204 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 4 ms 460 KB Output is correct
7 Correct 97 ms 5268 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 3 ms 460 KB Output is correct
10 Correct 70 ms 5352 KB Output is correct
11 Correct 65 ms 5228 KB Output is correct
12 Correct 65 ms 5488 KB Output is correct
13 Correct 68 ms 5312 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 4 ms 460 KB Output is correct
7 Correct 97 ms 5268 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 3 ms 460 KB Output is correct
10 Correct 70 ms 5352 KB Output is correct
11 Correct 65 ms 5228 KB Output is correct
12 Correct 65 ms 5488 KB Output is correct
13 Correct 68 ms 5312 KB Output is correct
14 Correct 100 ms 6696 KB Output is correct
15 Correct 567 ms 17276 KB Output is correct
16 Correct 100 ms 6596 KB Output is correct
17 Correct 559 ms 17200 KB Output is correct
18 Correct 393 ms 16780 KB Output is correct
19 Correct 418 ms 17164 KB Output is correct
20 Correct 514 ms 17224 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 63 ms 4956 KB Output is correct
4 Correct 326 ms 16984 KB Output is correct
5 Correct 367 ms 16584 KB Output is correct
6 Correct 563 ms 16888 KB Output is correct
7 Correct 603 ms 16952 KB Output is correct
8 Correct 568 ms 17120 KB Output is correct
9 Correct 340 ms 16696 KB Output is correct
10 Correct 361 ms 16460 KB Output is correct
11 Correct 281 ms 16332 KB Output is correct
12 Correct 328 ms 16564 KB Output is correct
13 Correct 388 ms 16628 KB Output is correct

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Incorrect 1 ms 204 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Incorrect 1 ms 204 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Incorrect 1 ms 204 KB Output isn't correct
5 Halted 0 ms 0 KB -