Submission #596143

#	Time	Username	Problem	Language	Result	Execution time	Memory
596143		jjang36524	Sushi (JOI16_sushi)	C++14	100 / 100	9482 ms	7232 KiB

sushi

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;
vector<int>pos;
int arr[400100];
struct pq
{
	int* q;
	int r;
	void init(vector<int>v)
	{
		q = (int*)calloc(v.size() + 2, sizeof(int));
		int i;
		for (i = 0; i < v.size(); i++)
			q[i + 1] = v[i];
		r = v.size();
	}
	inline int up(int n)
	{
		if (q[1] <= n)
		{
			return n;
		}
		int rv = q[1];

		int i = 1;
	T:
		if (i * 2 > r)
		{
			q[i] = n;
			return rv;
		}
		int v = i * 2 + (q[i * 2] <= q[i * 2 + 1]);
		if (q[v] <= n)
		{
			q[i] = n;
			return rv;
		}
		q[i] = q[v];
		i = v;
		goto T;
	}
};
pq poss[50100];
int q[25100][3];
map<pair<int, int>, int>t;
int main()
{
	int N, M;
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> N >> M;
	int i;
	for (i = 0; i < N; i++)
	{
		cin >> arr[i];
	}
	for (i = 0; i < M; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		a--;
		b--;
		q[i][0] = a;
		q[i][1] = b;
		q[i][2] = c;
		pos.push_back(a);
		pos.push_back(b + 1);
	}
	pos.push_back(0);
	pos.push_back(N);
	sort(pos.begin(), pos.end());
	pos.erase(unique(pos.begin(), pos.end()), pos.end());
	for (i = 0; i < pos.size() - 1; i++)
	{
		vector<int>x;
		int j;
		for (j = pos[i]; j < pos[i + 1]; j++)
		{
			x.push_back(arr[j]);
		}
		sort(x.begin(), x.end());
		reverse(x.begin(), x.end());
		poss[i].init(x);
	}
	int lm = pos.size() - 1;
	for (i = 0; i < M; i++)
	{
		int a = lower_bound(pos.begin(), pos.end(), q[i][0]) - pos.begin();
		int b = lower_bound(pos.begin(), pos.end(), q[i][1] + 1) - pos.begin();
		int j;
		int c = q[i][2];
		if (q[i][0] > q[i][1])
		{

			for (j = a; j < lm; j++)
			{
				c = poss[j].up(c);
			}
			for (j = 0; j < b; j++)
			{
				c = poss[j].up(c);
			}

		}
		else
		{
			for (j = a; j < b; j++)
			{
				c = poss[j].up(c);
			}
		}
		cout << c << '\n';
	}
}

Compilation message (stderr)

sushi.cpp: In member function 'void pq::init(std::vector<int>)':
sushi.cpp:16:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |   for (i = 0; i < v.size(); i++)
      |               ~~^~~~~~~~~~
sushi.cpp: In function 'int main()':
sushi.cpp:76:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |  for (i = 0; i < pos.size() - 1; i++)
      |              ~~^~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3: 80 / 80