oj.uz

Submission #1039857

# Submission time Handle Problem Language Result Execution time Memory
1039857 2024-07-31T10:51:45 Z parsadox2 Comparing Plants (IOI20_plants) C++17
44 / 100
 639 ms 28656 KB 
#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++)
	{
		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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10844 KB Output is correct
2 Correct 1 ms 10844 KB Output is correct
3 Correct 1 ms 10844 KB Output is correct
4 Incorrect 1 ms 10844 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 10844 KB Output is correct
2 Correct 1 ms 10844 KB Output is correct
3 Correct 1 ms 10844 KB Output is correct
4 Correct 2 ms 10844 KB Output is correct
5 Correct 2 ms 10844 KB Output is correct
6 Correct 4 ms 10932 KB Output is correct
7 Correct 43 ms 15696 KB Output is correct
8 Correct 2 ms 10844 KB Output is correct
9 Correct 4 ms 10844 KB Output is correct
10 Correct 43 ms 15700 KB Output is correct
11 Correct 40 ms 15564 KB Output is correct
12 Correct 37 ms 15700 KB Output is correct
13 Correct 41 ms 15612 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10844 KB Output is correct
2 Correct 1 ms 10844 KB Output is correct
3 Correct 1 ms 10844 KB Output is correct
4 Correct 2 ms 10844 KB Output is correct
5 Correct 2 ms 10844 KB Output is correct
6 Correct 4 ms 10932 KB Output is correct
7 Correct 43 ms 15696 KB Output is correct
8 Correct 2 ms 10844 KB Output is correct
9 Correct 4 ms 10844 KB Output is correct
10 Correct 43 ms 15700 KB Output is correct
11 Correct 40 ms 15564 KB Output is correct
12 Correct 37 ms 15700 KB Output is correct
13 Correct 41 ms 15612 KB Output is correct
14 Correct 76 ms 15852 KB Output is correct
15 Correct 639 ms 28556 KB Output is correct
16 Correct 82 ms 15952 KB Output is correct
17 Correct 614 ms 28652 KB Output is correct
18 Correct 355 ms 28592 KB Output is correct
19 Correct 357 ms 28496 KB Output is correct
20 Correct 505 ms 28504 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10844 KB Output is correct
2 Correct 1 ms 10844 KB Output is correct
3 Correct 34 ms 13476 KB Output is correct
4 Correct 293 ms 28648 KB Output is correct
5 Correct 402 ms 28592 KB Output is correct
6 Correct 490 ms 28496 KB Output is correct
7 Correct 574 ms 28656 KB Output is correct
8 Correct 633 ms 28632 KB Output is correct
9 Correct 346 ms 28500 KB Output is correct
10 Correct 346 ms 28640 KB Output is correct
11 Correct 248 ms 28640 KB Output is correct
12 Correct 310 ms 28620 KB Output is correct
13 Correct 353 ms 28588 KB Output is correct

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10840 KB Output is correct
2 Correct 1 ms 10844 KB Output is correct
3 Incorrect 1 ms 10844 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 10844 KB Output is correct
2 Correct 1 ms 10844 KB Output is correct
3 Incorrect 1 ms 10844 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 10844 KB Output is correct
2 Correct 1 ms 10844 KB Output is correct
3 Correct 1 ms 10844 KB Output is correct
4 Incorrect 1 ms 10844 KB Output isn't correct
5 Halted 0 ms 0 KB -