oj.uz

Submission #745022

# Submission time Handle Problem Language Result Execution time Memory
745022 2023-05-19T10:10:58 Z b00norp New Home (APIO18_new_home) C++14
5 / 100
 5000 ms 97132 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

const int INF = 1e18;

bool cmp(array<int, 4> a, array<int, 4> b)
{
	if(a[0] == b[0])
	{
		return a[3] < b[3];
	}
	return a[0] < b[0];
}

void Solve() 
{
	int n, k, q;
	cin >> n >> k >> q;
	vector<array<int, 3> > stores[k + 1];
	map<int, int> mp;
	for(int i = 1; i <= n; i++)
	{
		int x, type, st, fi;
		cin >> x >> type >> st >> fi;
		fi += 1;
		stores[type].push_back({x, st, fi});
		mp[st]++;
		mp[fi]++;
	}	
	vector<array<int, 2> > queries(q);
	for(int i = 0; i < q; i++)
	{
		cin >> queries[i][0] >> queries[i][1];
		mp[queries[i][1]]++;
	}
	int cnt = 1;
	for(auto i: mp)
	{
		mp[i.first] = cnt++;
	}
	vector<array<int, 4> > chronological_order;
	for(int i = 1; i <= k; i++)
	{
		for(auto [x, st, fi]: stores[i])
		{
			st = mp[st];
			fi = mp[fi];
			chronological_order.push_back({st, i, x, 0});
			chronological_order.push_back({fi, -i, x, 0});
		}
	}
	cnt = 0;
	for(auto [x, year]: queries)
	{
		year = mp[year];
		chronological_order.push_back({year, cnt++, x, 1});
	}
	sort(chronological_order.begin(), chronological_order.end(), cmp);
	multiset<int> opened_shops[k + 1];
	vector<int> res(q);
	for(auto [year, idx, x, type]: chronological_order)
	{
		if(type == 0)
		{
			if(idx < 0)
			{
				idx = -idx;
				opened_shops[idx].erase(opened_shops[idx].find(x));
			}
			else
			{
				opened_shops[idx].insert(x);
			}
		}
		else
		{
			int ans = 0;
			for(int i = 1; i <= k; i++)
			{
				if(opened_shops[i].size() == 0)
				{
					ans = -1;
					break;
				}
				auto it = lower_bound(opened_shops[i].begin(), opened_shops[i].end(), x);
				int cur_ans = 1e18;
				if(it != opened_shops[i].end())
				{
					cur_ans = min(cur_ans, abs(*(it) - x));
				}
				if(it != opened_shops[i].begin())
				{
					it = prev(it);
				}
				cur_ans = min(cur_ans, abs(*(it) - x));
				ans = max(ans, cur_ans);
			}
			res[idx] = ans;
		}
	}
	for(int i = 0; i < q; i++)
	{
		cout << res[i] << "\n";
	}
}

int32_t main() 
{
	auto begin = std::chrono::high_resolution_clock::now();
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t = 1;
	// cin >> t;
	for(int i = 1; i <= t; i++) 
	{
		//cout << "Case #" << i << ": ";
		Solve();
	}
	auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    //cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
	return 0;
}

/*
Sample 1:
4 2 4
3 1 1 10
9 2 2 4
7 2 5 7
4 1 8 10
5 3
5 6
5 9
1 10

Sample 2:
2 1 3
1 1 1 4
1 1 2 6 
1 3
1 5
1 7

Sample 3:
1 1 1
100000000 1 1 1
1 1

*/

Compilation message

new_home.cpp: In function 'void Solve()':
new_home.cpp:47:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   47 |   for(auto [x, st, fi]: stores[i])
      |            ^
new_home.cpp:56:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   56 |  for(auto [x, year]: queries)
      |           ^
new_home.cpp:64:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   64 |  for(auto [year, idx, x, type]: chronological_order)
      |           ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 3 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 2 ms 468 KB Output is correct
16 Correct 2 ms 468 KB Output is correct
17 Correct 2 ms 468 KB Output is correct
18 Correct 2 ms 468 KB Output is correct
19 Correct 2 ms 468 KB Output is correct
20 Correct 1 ms 468 KB Output is correct
21 Correct 2 ms 468 KB Output is correct
22 Correct 2 ms 468 KB Output is correct
23 Correct 2 ms 468 KB Output is correct
24 Correct 2 ms 468 KB Output is correct
25 Correct 1 ms 468 KB Output is correct
26 Correct 1 ms 468 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 1 ms 468 KB Output is correct
29 Correct 1 ms 468 KB Output is correct
30 Correct 1 ms 468 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 3 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 2 ms 468 KB Output is correct
16 Correct 2 ms 468 KB Output is correct
17 Correct 2 ms 468 KB Output is correct
18 Correct 2 ms 468 KB Output is correct
19 Correct 2 ms 468 KB Output is correct
20 Correct 1 ms 468 KB Output is correct
21 Correct 2 ms 468 KB Output is correct
22 Correct 2 ms 468 KB Output is correct
23 Correct 2 ms 468 KB Output is correct
24 Correct 2 ms 468 KB Output is correct
25 Correct 1 ms 468 KB Output is correct
26 Correct 1 ms 468 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 1 ms 468 KB Output is correct
29 Correct 1 ms 468 KB Output is correct
30 Correct 1 ms 468 KB Output is correct
31 Execution timed out 5064 ms 23828 KB Time limit exceeded
32 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5048 ms 82688 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5049 ms 97132 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 3 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 2 ms 468 KB Output is correct
16 Correct 2 ms 468 KB Output is correct
17 Correct 2 ms 468 KB Output is correct
18 Correct 2 ms 468 KB Output is correct
19 Correct 2 ms 468 KB Output is correct
20 Correct 1 ms 468 KB Output is correct
21 Correct 2 ms 468 KB Output is correct
22 Correct 2 ms 468 KB Output is correct
23 Correct 2 ms 468 KB Output is correct
24 Correct 2 ms 468 KB Output is correct
25 Correct 1 ms 468 KB Output is correct
26 Correct 1 ms 468 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 1 ms 468 KB Output is correct
29 Correct 1 ms 468 KB Output is correct
30 Correct 1 ms 468 KB Output is correct
31 Execution timed out 5064 ms 23828 KB Time limit exceeded
32 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 3 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 2 ms 468 KB Output is correct
16 Correct 2 ms 468 KB Output is correct
17 Correct 2 ms 468 KB Output is correct
18 Correct 2 ms 468 KB Output is correct
19 Correct 2 ms 468 KB Output is correct
20 Correct 1 ms 468 KB Output is correct
21 Correct 2 ms 468 KB Output is correct
22 Correct 2 ms 468 KB Output is correct
23 Correct 2 ms 468 KB Output is correct
24 Correct 2 ms 468 KB Output is correct
25 Correct 1 ms 468 KB Output is correct
26 Correct 1 ms 468 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 1 ms 468 KB Output is correct
29 Correct 1 ms 468 KB Output is correct
30 Correct 1 ms 468 KB Output is correct
31 Execution timed out 5064 ms 23828 KB Time limit exceeded
32 Halted 0 ms 0 KB -