oj.uz

Submission #595917

# Submission time Handle Problem Language Result Execution time Memory
595917 2022-07-14T08:03:48 Z 장태환(#8443) Sushi (JOI16_sushi) C++17
20 / 100
 12000 ms 11984 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
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);
	}
	inline int up(int n)
	{
		if (q[1] <= n)
		{
			return n;
		}
		int rv = q[1];

		int i = 1;
	T:
		i *= 2;
		if (q[i] <= q[i+ 1])
			i++;
		if (q[i] <= n)
		{
			q[i >> 1] = n;
			return rv;
		}
		q[i >> 1] = q[i];
		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:15:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |   for (i = 0; i < v.size(); i++)
      |               ~~^~~~~~~~~~
sushi.cpp: In function 'int main()':
sushi.cpp:70:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |  for (i = 0; i < pos.size() - 1; i++)
      |              ~~^~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2004 KB Output is correct
2 Correct 5 ms 2004 KB Output is correct
3 Correct 7 ms 2004 KB Output is correct
4 Correct 5 ms 2004 KB Output is correct
5 Correct 5 ms 2004 KB Output is correct
6 Correct 7 ms 2012 KB Output is correct
7 Correct 5 ms 2004 KB Output is correct
8 Correct 4 ms 1884 KB Output is correct
9 Correct 7 ms 2004 KB Output is correct
10 Correct 7 ms 2004 KB Output is correct
11 Correct 11 ms 2008 KB Output is correct
12 Correct 11 ms 2004 KB Output is correct
13 Correct 10 ms 2016 KB Output is correct
14 Correct 5 ms 2004 KB Output is correct
15 Correct 6 ms 2004 KB Output is correct
16 Correct 3 ms 2004 KB Output is correct
17 Correct 1 ms 1876 KB Output is correct
18 Correct 1 ms 1876 KB Output is correct
19 Correct 1 ms 1876 KB Output is correct
20 Correct 1 ms 1876 KB Output is correct
21 Correct 1 ms 1876 KB Output is correct
22 Correct 1 ms 1876 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 11820 KB Output is correct
2 Correct 78 ms 11864 KB Output is correct
3 Correct 52 ms 11876 KB Output is correct
4 Correct 93 ms 11792 KB Output is correct
5 Correct 63 ms 11844 KB Output is correct
6 Correct 64 ms 11852 KB Output is correct
7 Correct 61 ms 11856 KB Output is correct
8 Correct 64 ms 11788 KB Output is correct
9 Correct 39 ms 11884 KB Output is correct
10 Correct 51 ms 11868 KB Output is correct
11 Correct 41 ms 11844 KB Output is correct
12 Correct 57 ms 11840 KB Output is correct
13 Correct 88 ms 11796 KB Output is correct
14 Correct 81 ms 11788 KB Output is correct
15 Correct 56 ms 11984 KB Output is correct
16 Correct 108 ms 11796 KB Output is correct
17 Correct 63 ms 11904 KB Output is correct
18 Correct 77 ms 11828 KB Output is correct
19 Correct 75 ms 11792 KB Output is correct
20 Correct 84 ms 11788 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2004 KB Output is correct
2 Correct 5 ms 2004 KB Output is correct
3 Correct 7 ms 2004 KB Output is correct
4 Correct 5 ms 2004 KB Output is correct
5 Correct 5 ms 2004 KB Output is correct
6 Correct 7 ms 2012 KB Output is correct
7 Correct 5 ms 2004 KB Output is correct
8 Correct 4 ms 1884 KB Output is correct
9 Correct 7 ms 2004 KB Output is correct
10 Correct 7 ms 2004 KB Output is correct
11 Correct 11 ms 2008 KB Output is correct
12 Correct 11 ms 2004 KB Output is correct
13 Correct 10 ms 2016 KB Output is correct
14 Correct 5 ms 2004 KB Output is correct
15 Correct 6 ms 2004 KB Output is correct
16 Correct 3 ms 2004 KB Output is correct
17 Correct 1 ms 1876 KB Output is correct
18 Correct 1 ms 1876 KB Output is correct
19 Correct 1 ms 1876 KB Output is correct
20 Correct 1 ms 1876 KB Output is correct
21 Correct 1 ms 1876 KB Output is correct
22 Correct 1 ms 1876 KB Output is correct
23 Correct 102 ms 11820 KB Output is correct
24 Correct 78 ms 11864 KB Output is correct
25 Correct 52 ms 11876 KB Output is correct
26 Correct 93 ms 11792 KB Output is correct
27 Correct 63 ms 11844 KB Output is correct
28 Correct 64 ms 11852 KB Output is correct
29 Correct 61 ms 11856 KB Output is correct
30 Correct 64 ms 11788 KB Output is correct
31 Correct 39 ms 11884 KB Output is correct
32 Correct 51 ms 11868 KB Output is correct
33 Correct 41 ms 11844 KB Output is correct
34 Correct 57 ms 11840 KB Output is correct
35 Correct 88 ms 11796 KB Output is correct
36 Correct 81 ms 11788 KB Output is correct
37 Correct 56 ms 11984 KB Output is correct
38 Correct 108 ms 11796 KB Output is correct
39 Correct 63 ms 11904 KB Output is correct
40 Correct 77 ms 11828 KB Output is correct
41 Correct 75 ms 11792 KB Output is correct
42 Correct 84 ms 11788 KB Output is correct
43 Correct 1799 ms 8256 KB Output is correct
44 Correct 1570 ms 8248 KB Output is correct
45 Correct 1590 ms 8056 KB Output is correct
46 Correct 1506 ms 8244 KB Output is correct
47 Correct 1537 ms 8252 KB Output is correct
48 Correct 8636 ms 8164 KB Output is correct
49 Correct 8918 ms 8168 KB Output is correct
50 Correct 8592 ms 8232 KB Output is correct
51 Correct 8255 ms 8144 KB Output is correct
52 Correct 1370 ms 7912 KB Output is correct
53 Correct 2889 ms 8172 KB Output is correct
54 Execution timed out 12025 ms 8220 KB Time limit exceeded
55 Halted 0 ms 0 KB -