Submission #300910

#	Time	Username	Problem	Language	Result	Execution time	Memory
300910		CodePlatina	Comparing Plants (IOI20_plants)	C++14	44 / 100	1068 ms	13432 KiB

plants

#include "plants.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <utility>
#define pii pair<int, int>
#define piii pair<int, pii>
#define pll pair<long long, long long>
#define plll pair<long long, pll>
#define ff first
#define ss second
#define ee ss.ff
#define rr ss.ss

using namespace std;

struct Node
{
    pii mn, lazy;
}seg[808080];

void prop(int ind)
{
    Node &x = seg[ind << 1], &y = seg[ind << 1 | 1], &nd = seg[ind];
    if(nd.lazy.ff)
    {
        x.mn.ff += nd.lazy.ff;
        y.mn.ff += nd.lazy.ff;
        x.lazy.ff += nd.lazy.ff;
        y.lazy.ff += nd.lazy.ff;
        nd.lazy.ff = 0;
    }
    if(nd.lazy.ss)
    {
        x.mn.ss += nd.lazy.ss;
        y.mn.ss += nd.lazy.ss;
        x.lazy.ss += nd.lazy.ss;
        y.lazy.ss += nd.lazy.ss;
        nd.lazy.ss = 0;
    }
}

void mrge(int ind)
{
    seg[ind].mn = min(seg[ind << 1].mn, seg[ind << 1 | 1].mn);
}

void init_seg(vector<int> &r, int ind, int s, int e)
{
    if(s + 1 == e)
    {
        seg[ind].mn = {r[s], 0};
        seg[ind].lazy = {0, 0};
        return;
    }

    int mid = s + e >> 1;
    init_seg(r, ind << 1, s, mid);
    init_seg(r, ind << 1 | 1, mid, e);
    mrge(ind);
}

void upd1(int ind, int s, int e, int l, int r, int x)
{
    if(e <= l || r <= s) return;
    if(l <= s && e <= r)
    {
        seg[ind].mn.ff += x;
        seg[ind].lazy.ff += x;
        return;
    }

    prop(ind);
    int mid = s + e >> 1;
    upd1(ind << 1, s, mid, l, r, x);
    upd1(ind << 1 | 1, mid, e, l, r, x);
    mrge(ind);
}

void upd2(int ind, int s, int e, int l, int r, int x)
{
    if(e <= l || r <= s) return;
    if(l <= s && e <= r)
    {
        seg[ind].mn.ss += x;
        seg[ind].lazy.ss += x;
        return;
    }

    prop(ind);
    int mid = s + e >> 1;
    upd2(ind << 1, s, mid, l, r, x);
    upd2(ind << 1 | 1, mid, e, l, r, x);
    mrge(ind);
}

void qr1(vector<int> &ret, int ind, int s, int e, int l, int r)
{
    if(e <= l || r <= s || seg[ind].mn.ff) return;
    if(s + 1 == e)
    {
        ret.push_back(s);
        return;
    }

    prop(ind);
    int mid = s + e >> 1;
    qr1(ret, ind << 1, s, mid, l, r);
    qr1(ret, ind << 1 | 1, mid, e, l, r);
}

int qr2(int ind, int s, int e)
{
    if(s + 1 == e) return s;

    prop(ind);
    int mid = s + e >> 1;
    if(seg[ind << 1].mn == pii{0, 0}) return qr2(ind << 1, s, mid);
    else return qr2(ind << 1 | 1, mid, e);
}

int N, K;
int ord[202020];

void init(int k, vector<int> r)
{
	N = r.size(); K = k;
	init_seg(r, 1, 0, N);
	for(int i = 0; i <= N - K; ++i) if(!r[i]) upd2(1, 0, N, i + 1, i + K, 1);
	for(int i = N - K + 1; i < N; ++i) if(!r[i]) upd2(1, 0, N, i + 1, N, 1), upd2(1, 0, N, 0, K - N + i, 1);

	for(int i = 0; i < N; ++i)
    {
        int t = qr2(1, 0, N);
        ord[t] = i;

        vector<int> ls;

        upd1(1, 0, N, t, t + 1, N);

        if(t >= K - 1)
        {
            upd1(1, 0, N, t - K + 1, t, -1);
            qr1(ls, 1, 0, N, t - K + 1, t);
        }
        else
        {
            upd1(1, 0, N, 0, t, -1);
            upd1(1, 0, N, N - K + t + 1, N, -1);
            qr1(ls, 1, 0, N, 0, t);
            qr1(ls, 1, 0, N, N - K + t + 1, N);
        }

        if(t <= N - K) upd2(1, 0, N, t + 1, t + K, -1);
        else
        {
            upd2(1, 0, N, t + 1, N, -1);
            upd2(1, 0, N, 0, K - N + t, -1);
        }

        for(int j : ls)
        {
            if(j <= N - K) upd2(1, 0, N, j + 1, j + K, 1);
            else
            {
                upd2(1, 0, N, j + 1, N, 1);
                upd2(1, 0, N, 0, K - N + j, 1);
            }
        }
    }

//    for(int i = 0; i < N; ++i)
//    {
//        for(int j = 0; j < N; ++j)
//        {
//            for(int k = 0; k < N; ++k)
//            {
//                if(arr[j][i] && arr[i][k]) arr[j][k] = true;
//            }
//        }
//    }

//    for(int i = 0; i < N; ++i)
//    {
//        for(int j = 0; j < N; ++j)
//        {
//            cout << arr[i][j];
//        }
//        cout << endl;
//    }
}

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

Compilation message (stderr)

plants.cpp: In function 'void init_seg(std::vector<int>&, int, int, int)':
plants.cpp:58:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   58 |     int mid = s + e >> 1;
      |               ~~^~~
plants.cpp: In function 'void upd1(int, int, int, int, int, int)':
plants.cpp:75:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   75 |     int mid = s + e >> 1;
      |               ~~^~~
plants.cpp: In function 'void upd2(int, int, int, int, int, int)':
plants.cpp:92:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   92 |     int mid = s + e >> 1;
      |               ~~^~~
plants.cpp: In function 'void qr1(std::vector<int>&, int, int, int, int, int)':
plants.cpp:108:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  108 |     int mid = s + e >> 1;
      |               ~~^~~
plants.cpp: In function 'int qr2(int, int, int)':
plants.cpp:118:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  118 |     int mid = s + e >> 1;
      |               ~~^~~

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