Submission #1039856

#	Time	Username	Problem	Language	Result	Execution time	Memory
1039856		parsadox2	Comparing Plants (IOI20_plants)	C++17	0 / 100	42 ms	15792 KiB

plants

#include "plants.h"
#include <bits/stdc++.h>

#define F first
#define S second

using namespace std;

const int N = 2e5 + 10;

int n , k , pos[N];
vector <int> a;

pair<pair<int , int> , int> tup(int aa , int bb , int cc)
{
	return make_pair(make_pair(aa , bb) , cc);
}

struct SEG{
	pair<pair<int , int> , int> mn[N << 2];
	pair <int , int> lzy[N << 2];
	void Build(int node = 1 , int nl = 0 , int nr = n)
	{
		lzy[node] = make_pair(0 , 0);
		if(nr - nl == 1)
		{
			mn[node] = tup(a[nl] , 0 , nl);
			return;
		}
		int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
		Build(lc , nl , mid);  Build(rc , mid , nr);
		mn[node] = min(mn[lc] , mn[rc]);
	}
	void Shift(int node , int lc , int rc)
	{
		if(lzy[node].F != 0)
		{
			mn[lc].F.F += lzy[node].F;
			mn[rc].F.F += lzy[node].F;
			lzy[lc].F += lzy[node].F;
			lzy[rc].F += lzy[node].F;
			lzy[node].F = 0;
		}
		if(lzy[node].S != 0)
		{
			mn[lc].F.S += lzy[node].S;
			mn[rc].F.S += lzy[node].S;
			lzy[lc].S += lzy[node].S;
			lzy[rc].S += lzy[node].S;
			lzy[node].S = 0;
		}
	}
	void Add(int ty , int val , int l , int r , int node = 1 , int nl = 0 , int nr = n)
	{
		if(r <= nl || nr <= l)
			return;
		if(l <= nl && nr <= r)
		{
			if(ty == 1)
			{
				lzy[node].F += val;
				mn[node].F.F += val;
				return;
			}
			else
			{
				lzy[node].S += val;
				mn[node].F.S += val;
				return;
			}
		}
		int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
		Shift(node , lc , rc);
		Add(ty , val , l , r , lc , nl , mid);
		Add(ty , val , l , r , rc , mid , nr);
		mn[node] = min(mn[lc] , mn[rc]);
	}
	void Debug(int node = 1 , int nl = 0 , int nr = n)
	{
		cout << nl << " --- " << nr << " : " << mn[node].F.F << " " << mn[node].F.S << " " << mn[node].S << endl;
		cout << lzy[node].F << " " << lzy[node].S << endl;
		if(nr - nl == 1)
			return;
		int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
		Debug(lc , nl , mid);  Debug(rc , mid , nr);
	}
} seg;

struct SEG2{
	pair<int , int> mn[N << 2];
	int lzy[N << 2];
	void Build(int node = 1 , int nl = 0 , int nr = n)
	{
		lzy[node] = 0;
		if(nr - nl == 1)
		{
			mn[node] = make_pair(a[nl] , nl);
			return;
		}
		int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
		Build(lc , nl , mid);  Build(rc , mid , nr);
		mn[node] = min(mn[lc] , mn[rc]);
	}
	void Shift(int node , int lc , int rc)
	{
		if(lzy[node] == 0)
			return;
		mn[lc].F += lzy[node];
		mn[rc].F += lzy[node];
		lzy[lc] += lzy[node];
		lzy[rc] += lzy[node];
		lzy[node] = 0;
	}
	void Add(int ty , int val , int l , int r , int node = 1 , int nl = 0 , int nr = n)
	{
		if(r <= nl || nr <= l || ty == 2)
			return;
		if(l <= nl && nr <= r)
		{
			mn[node].F += val;
			lzy[node] += val;
			return;
		}
		int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
		Shift(node , lc , rc);
		Add(ty , val , l , r , lc , nl , mid);  Add(ty , val , l , r , rc , mid , nr);
		mn[node] = min(mn[lc] , mn[rc]);
	}
} seg2;

void Add(int ty , int val , int l , int r)
{
	if(l >= 0 && r <= n)
	{
		seg.Add(ty , val , l , r);
		return;
	}
	if(l < 0)
	{
		seg.Add(ty , val , n + l , n);
		if(r != 0)
		{
			seg.Add(ty , val , 0 , r);
		}
		return;
	}
	if(r > n)
	{
		seg.Add(ty , val , 0 , r - n);
		if(l != n)
		{
			seg.Add(ty , val , l , n);
		}
	}
}

void Add2(int ty , int val , int l , int r)
{
	if(l >= 0 && r <= n)
	{
		seg2.Add(ty , val , l , r);
		return;
	}
	if(l < 0)
	{
		seg2.Add(ty , val , n + l , n);
		if(r != 0)
		{
			seg2.Add(ty , val , 0 , r);
		}
		return;
	}
	if(r > n)
	{
		seg2.Add(ty , val , 0 , r - n);
		if(l != n)
		{
			seg2.Add(ty , val , l , n);
		}
	}
}

void init(int kk, vector<int> r) {
	a = r;
	k = kk;
	n = r.size();
	seg.Build();
	seg2.Build();
	for(int i = 0 ; i < n ; i++)  if(a[i] == 0)
		Add(2 , 1 , i + 1 , i + k);
	for(int i = 0 ; i < n ; i++)
	{
		while(seg2.mn[1].F == 0)
		{
			int id = seg2.mn[1].S;
			Add(2 , 1 , id + 1 , id + k);
			Add2(1 , N , id , id + 1);
		}
		auto now = seg.mn[1];
		int id = now.S;
		Add(1 , -1 , id - k + 1 , id);
		Add2(1 , -1 , id - k + 1 , id);
		Add(1 , N , id , id + 1);
		Add(2 , -1 , id + 1 , id + k);
		//cout << "DEBUG " << endl;
		//seg.Debug();
		pos[id] = i;
	}
	return;
}

int compare_plants(int x, int y) {
	return (pos[x] < pos[y] ? 1 : -1);
}

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