Submission #1078885

#	Time	Username	Problem	Language	Result	Execution time	Memory
1078885		quangminh412	Stone Arranging 2 (JOI23_ho_t1)	C++14	25 / 100	2101 ms	26228 KiB

Main

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

/*
  John Watson
  https://codeforces.com/profile/quangminh98

  Mua Code nhu mua Florentino !!
*/

#define faster() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long

const int maxn = 2e5 + 9;
const int segsize = 4 * maxn;

int n;
int arr[maxn];

class SegmentTree
{
	struct Node
	{
		int sum;
		int lazy;
		
		Node(int sum = 0, int lazy = -1) : sum(sum), lazy(lazy) {}
		
		Node operator + (const Node& other)
		{
			Node res;
			res.sum = sum + other.sum;
			res.lazy = -1;
			return res;
		}
	};
	
	vector<Node> st;
	int n;
	
	void pass(int head, int l, int r)
	{
		if (st[head].lazy == -1 || l == r) return;
		
		int mid = l + r >> 1;
		st[2 * head].sum = (mid - l + 1) * st[head].lazy;
		st[2 * head + 1].sum = (r - mid) * st[head].lazy;
		st[2 * head].lazy = st[head].lazy;
		st[2 * head + 1].lazy = st[head].lazy;
		
		st[head].lazy = -1;
	}
	
	void update(int head, int l, int r, int u, int v, int val)
	{
		pass(head, l, r);
		if (l > v || r < u) return;
		if (u <= l && r <= v) 
		{
			st[head].sum = (r - l + 1) * val;
			st[head].lazy = val;
			return;
		}
		
		int mid = l + r >> 1;
		update(2 * head, l, mid, u, v, val);
		update(2 * head + 1, mid + 1, r, u, v, val);
		
		st[head] = st[2 * head] + st[2 * head + 1];
	}
	
	int query(int head, int l, int r, int u, int v)
	{
		if (u > v) return -1;
		pass(head, l, r);
		
		if (l > v || r < u) return -1;
		if (l == r && st[head].sum > 0) return l;
		
		int mid = l + r >> 1;
		return max(query(2 * head, l, mid, u, v), query(2 * head + 1, mid + 1, r, u, v));
	}
	
	int getpos(int head, int l, int r, int pos)
	{
		if (l == r) 
			return st[head].sum;
			
		int mid = l + r >> 1;
		if (pos <= mid)
			return getpos(2 * head, l, mid, pos);
		return getpos(2 * head + 1, mid + 1, r, pos);
	}
public:
	SegmentTree(int n = 0) : n(n) { st.resize(segsize, Node(0, -1)); }
	
	void update(int u, int v, int val) { update(1, 1, n, u, v, val); }
	int query(int u, int v) { return query(1, 1, n, u, v); }
	int getpos(int pos) { return getpos(1, 1, n, pos); }
};

void solve_2()
{
	SegmentTree seg[3];
	for (int i = 1; i < 3; i++) seg[i] = SegmentTree(n);
	
	for (int i = 1; i <= n; i++)
	{
		int pos = seg[arr[i]].query(1, i - 1);
		
		if (pos != -1)
		{
			seg[arr[i]].update(pos, i - 1, 1);
			seg[3 - arr[i]].update(pos, i - 1, 0);
		}
		
		seg[arr[i]].update(i, i, 1);
	}

	for (int i = 1; i <= n; i++)
	{
		int pos1 = seg[1].getpos(i);
		int pos2 = seg[2].getpos(i);
		
		cout << (pos1 == 1 ? 1 : 2) << '\n';
	}
}

void solve_1()
{
	for (int i = 1; i <= n; i++)
	{
		int mx = -1;
		for (int j = 1; j < i; j++)
			if (arr[j] == arr[i])
				mx = max(mx, j);
		if (mx != -1)
			for (int j = mx; j < i; j++)
				arr[j] = arr[i];	
	}
	for (int i = 1; i <= n; i++)
		cout << arr[i] << '\n';
}

signed main()
{
	if (fopen("test.inp", "r"))
	{
		freopen("test.inp", "r", stdin);
		freopen("test.out", "w", stdout);
	}
	faster();

	cin >> n;
	
	bool sub2 = true;
	for (int i = 1; i <= n; i++)
	{
		cin >> arr[i];
		if (arr[i] > 2) sub2 = false;
	}

	if (n <= 2000)
	{
		solve_1();
		return 0;
	}
	if (sub2 == true)
	{
		solve_2();
		return 0;
	}

	return 0;
}

Compilation message (stderr)

Main.cpp: In member function 'void SegmentTree::pass(int, int, int)':
Main.cpp:45:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   45 |   int mid = l + r >> 1;
      |             ~~^~~
Main.cpp: In member function 'void SegmentTree::update(int, int, int, int, int, int)':
Main.cpp:65:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   65 |   int mid = l + r >> 1;
      |             ~~^~~
Main.cpp: In member function 'int SegmentTree::query(int, int, int, int, int)':
Main.cpp:80:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   80 |   int mid = l + r >> 1;
      |             ~~^~~
Main.cpp: In member function 'int SegmentTree::getpos(int, int, int, int)':
Main.cpp:89:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   89 |   int mid = l + r >> 1;
      |             ~~^~~
Main.cpp: In function 'void solve_2()':
Main.cpp:123:7: warning: unused variable 'pos2' [-Wunused-variable]
  123 |   int pos2 = seg[2].getpos(i);
      |       ^~~~
Main.cpp: In function 'int main()':
Main.cpp:149:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  149 |   freopen("test.inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:150:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  150 |   freopen("test.out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 25 / 25
• Subtask 2: 0 / 35
• Subtask 3: 0 / 40