Submission #422164

#	Time	Username	Problem	Language	Result	Execution time	Memory
422164		idk321	Comparing Plants (IOI20_plants)	C++17	32 / 100	508 ms	11116 KiB

plants

#include "plants.h"

#include <bits/stdc++.h>
using namespace std;

int k;
vector<int> r;
vector<int> prefR;
const int N = 200005;
int tree[4 * N];
int lazy[4 * N];
const int M = 1000000000;


int n;
int getSum(int from, int to)
{
    int res = prefR[to + 1];
    res -= prefR[from];
    return res;
}

void push(int node)
{
    for (int i = 0; i <= 1; i++)
    {
        tree[node * 2 +i] += lazy[node];
        lazy[node * 2 + i] += lazy[node];
    }
    lazy[node] = 0;
}

void add(int num, int from, int to, int a, int b, int node)
{
    if (from <= a && b <= to)
    {
        tree[node] += num;
        lazy[node] += num;
        return;
    }

    push(node);
    int mid = (a + b) / 2;
    if (from <= mid) add(num, from, to, a, mid, node * 2);
    if (to > mid) add(num, from, to, mid + 1, b, node * 2+ 1);

    if (tree[node * 2] <= tree[node * 2 +1])
    {

        tree[node] = tree[node * 2];
    } else
    {

        tree[node] = tree[node * 2 + 1];
    }
}

int minIndOn(int from, int to, int a, int b, int node)
{
    if(tree[node] != 0) return -1;
    if (a == b)
    {
        return a;
    }

    push(node);
    int mid = (a + b) / 2;
    int res = -1;
    if (from <= mid) res = minIndOn(from, to, a, mid, node * 2);
    if (res == -1 && to > mid) res = minIndOn(from, to, mid + 1, b, node * 2 + 1);

    return res;
}

vector<int> order;

void init(int K, std::vector<int> R) {
    k = K;
    r = R;
    n = r.size();
    prefR.resize(r.size() + 1);
    for (int i = 1; i <= r.size(); i++)
    {
        prefR[i] = r[i - 1];
        prefR[i] += prefR[i - 1];
    }

    order.resize(n);


    if (k == 2) return;

    for (int i = 0; i < n; i++)
    {
        add(r[i], i, i, 0, n - 1, 1);
    }

    for (int t = 0; t < n; t++)
    {
        int res = -1;

        int res1 = minIndOn(0, n - 1, 0, n - 1, 1);


        if (res1 + k <= n - 1)
        {
            int res2 = minIndOn(res1 + k, n - 1, 0, n - 1, 1);

            if (res2 != -1) res = res2;
            else res = res1;
        } else res = res1;



        order[res] = t;
        add(M, res, res, 0, n - 1, 1);

        if (res != 0) add(-1, max(0, res - k + 1), res - 1, 0, n - 1, 1);
        int still = k - (res - max(0, res - k + 1) + 1);
        if (still > 0)
        {
            add(-1, n - still, n - 1, 0, n - 1, 1);
        }


    }



	return;
}

int compare_plants(int x, int y) {
    if (k == 2)
    {
        if (getSum(x, y - 1) == (y - x)) return -1;
        if (getSum(x, y - 1) == 0) return 1;
        int sum1 = getSum(y, n -1);
        if (x != 0) sum1 += getSum(0, x - 1);
        if (sum1 == (n - y) + x) return 1;
        if (sum1 == 0) return -1;
        return 0;
    }


    if (order[x] < order[y])
    {
        return 1;
    }
    if (order[x] > order[y]) return -1;

	return 0;
}

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

Compilation message (stderr)

plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:82:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |     for (int i = 1; i <= r.size(); i++)
      |                     ~~^~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 14 / 14
• Subtask 3: 13 / 13
• Subtask 4: 0 / 17
• Subtask 5: 0 / 11
• Subtask 6: 0 / 15
• Subtask 7: 0 / 25