oj.uz

Submission #595885

# Submission time Handle Problem Language Result Execution time Memory
595885 2022-07-14T07:52:23 Z 장태환(#8443) Sushi (JOI16_sushi) C++17
15 / 100
 92 ms 13836 KB 
#include <bits/stdc++.h>
using namespace std;
vector<int>pos;
int arr[400100];
struct pq
{
	vector<int>q;
	int ca = 0;
	void init(vector<int>v)
	{
		q.push_back(0);
		int i;
		for (i = 0; i < v.size(); i++)
			q.push_back(v[i]);
		q.resize(q.size() * 2);
		if (v.size() <= 3)
			ca = 1;
	}
	inline int up(int n)
	{
		if (q[1] <= n)
		{
			return n;
		}
		if (ca)
		{
			int i = 1;
			while (q[i]>n)
			{
				q[i + 1] = q[i];
				i++;
			}
			q[i] = n;
		}
		int rv = q[1];

		int i = 1;
	T:
		if (q[i * 2] <= q[i * 2 + 1])
		{
			if (q[i * 2 + 1] <= n)
			{
				q[i] = n;
				return rv;
			}
			q[i] = q[i * 2 + 1];
			i = i * 2 + 1;
		}
		else
		{
			if (q[i * 2] <= n)
			{
				q[i] = n;
				return rv;
			}
			q[i] = q[i * 2];
			i = i * 2;
		}
		goto T;
	}
};
pq poss[50100];
int q[25100][3];
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

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

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 3924 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 13836 KB Output is correct
2 Correct 81 ms 13604 KB Output is correct
3 Correct 44 ms 12688 KB Output is correct
4 Correct 87 ms 13644 KB Output is correct
5 Correct 68 ms 13588 KB Output is correct
6 Correct 69 ms 13652 KB Output is correct
7 Correct 69 ms 13740 KB Output is correct
8 Correct 67 ms 13756 KB Output is correct
9 Correct 48 ms 12800 KB Output is correct
10 Correct 53 ms 13696 KB Output is correct
11 Correct 49 ms 12768 KB Output is correct
12 Correct 56 ms 13580 KB Output is correct
13 Correct 91 ms 13672 KB Output is correct
14 Correct 80 ms 13604 KB Output is correct
15 Correct 60 ms 12740 KB Output is correct
16 Correct 92 ms 13596 KB Output is correct
17 Correct 64 ms 13636 KB Output is correct
18 Correct 71 ms 13656 KB Output is correct
19 Correct 66 ms 13660 KB Output is correct
20 Correct 71 ms 13692 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 3924 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -