Submission #516787

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
516787	2022-01-22T06:20:02 Z	shmad	New Home (APIO18_new_home)	C++17	5 / 100	5000 ms	35064 KB

new_home

#pragma GCC optimize("O3", "unroll-loops")
#pragma GCC target("avx2", "bmi", "bmi2", "lzcnt", "popcnt") 

#include <bits/stdc++.h>

#define int long long
#define vt vector
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define ff first
#define ss second
#define dbg(x) cerr << #x << " = " << x << '\n'

using namespace std;
using ll = long long;
using pii = pair<int, int>;
using vvi = vt< vt<int> >;

const int N = 1e6 + 5, mod = 1e9 + 7, inf = 1e18 + 7, B = 500, LIM = (1ll << 17);
const double eps = 1e-6;

int n, k, q;

struct Event {
	int x, a, b;
};

vt<Event> g[N];

void solve () {
    cin >> n >> k >> q;
    for (int i = 1; i <= n; i++) {
		int x, t, a, b;
		cin >> x >> t >> a >> b;
		g[t].pb({x, a, b});
    }
    while (q--) {
    	int l, y;
    	cin >> l >> y;
    	int ans = 0;
    	for (int i = 1; i <= k; i++) {
    		int res = inf;
    		for (auto [x, a, b]: g[i]) {
    			if (a <= y && y <= b) res = min(res, abs(l - x));
    		}
    		ans = max(ans, res);
    	}
    	cout << (ans == inf ? -1 : ans) << '\n';
    }
    cout << '\n';
}

bool testcases = 0;
                  
signed main() {
    cin.tie(0) -> sync_with_stdio(0);
    int test = 1;
    if (testcases) cin >> test;
    for (int cs = 1; cs <= test; cs++) {
        solve ();         
    }
}

Subtask #1
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	14 ms	23756 KB	Output is correct
2	Correct	14 ms	23760 KB	Output is correct
3	Correct	14 ms	23732 KB	Output is correct
4	Correct	14 ms	23740 KB	Output is correct
5	Correct	18 ms	23756 KB	Output is correct
6	Correct	17 ms	23796 KB	Output is correct
7	Correct	15 ms	23812 KB	Output is correct
8	Correct	15 ms	23740 KB	Output is correct
9	Correct	15 ms	23756 KB	Output is correct
10	Correct	15 ms	23740 KB	Output is correct
11	Correct	15 ms	23756 KB	Output is correct
12	Correct	16 ms	23756 KB	Output is correct
13	Correct	15 ms	23712 KB	Output is correct
14	Correct	15 ms	23768 KB	Output is correct
15	Correct	14 ms	23820 KB	Output is correct
16	Correct	15 ms	23740 KB	Output is correct
17	Correct	15 ms	23756 KB	Output is correct
18	Correct	19 ms	23812 KB	Output is correct
19	Correct	15 ms	23756 KB	Output is correct
20	Correct	14 ms	23756 KB	Output is correct
21	Correct	15 ms	23756 KB	Output is correct
22	Correct	16 ms	23700 KB	Output is correct
23	Correct	15 ms	23808 KB	Output is correct
24	Correct	14 ms	23816 KB	Output is correct
25	Correct	15 ms	23792 KB	Output is correct
26	Correct	16 ms	23824 KB	Output is correct
27	Correct	17 ms	23756 KB	Output is correct
28	Correct	15 ms	23756 KB	Output is correct
29	Correct	14 ms	23756 KB	Output is correct
30	Correct	15 ms	23816 KB	Output is correct

Subtask #2
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	14 ms	23756 KB	Output is correct
2	Correct	14 ms	23760 KB	Output is correct
3	Correct	14 ms	23732 KB	Output is correct
4	Correct	14 ms	23740 KB	Output is correct
5	Correct	18 ms	23756 KB	Output is correct
6	Correct	17 ms	23796 KB	Output is correct
7	Correct	15 ms	23812 KB	Output is correct
8	Correct	15 ms	23740 KB	Output is correct
9	Correct	15 ms	23756 KB	Output is correct
10	Correct	15 ms	23740 KB	Output is correct
11	Correct	15 ms	23756 KB	Output is correct
12	Correct	16 ms	23756 KB	Output is correct
13	Correct	15 ms	23712 KB	Output is correct
14	Correct	15 ms	23768 KB	Output is correct
15	Correct	14 ms	23820 KB	Output is correct
16	Correct	15 ms	23740 KB	Output is correct
17	Correct	15 ms	23756 KB	Output is correct
18	Correct	19 ms	23812 KB	Output is correct
19	Correct	15 ms	23756 KB	Output is correct
20	Correct	14 ms	23756 KB	Output is correct
21	Correct	15 ms	23756 KB	Output is correct
22	Correct	16 ms	23700 KB	Output is correct
23	Correct	15 ms	23808 KB	Output is correct
24	Correct	14 ms	23816 KB	Output is correct
25	Correct	15 ms	23792 KB	Output is correct
26	Correct	16 ms	23824 KB	Output is correct
27	Correct	17 ms	23756 KB	Output is correct
28	Correct	15 ms	23756 KB	Output is correct
29	Correct	14 ms	23756 KB	Output is correct
30	Correct	15 ms	23816 KB	Output is correct
31	Execution timed out	5024 ms	27020 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	5088 ms	35064 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	5096 ms	34020 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #5
0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	14 ms	23756 KB	Output is correct
2	Correct	14 ms	23760 KB	Output is correct
3	Correct	14 ms	23732 KB	Output is correct
4	Correct	14 ms	23740 KB	Output is correct
5	Correct	18 ms	23756 KB	Output is correct
6	Correct	17 ms	23796 KB	Output is correct
7	Correct	15 ms	23812 KB	Output is correct
8	Correct	15 ms	23740 KB	Output is correct
9	Correct	15 ms	23756 KB	Output is correct
10	Correct	15 ms	23740 KB	Output is correct
11	Correct	15 ms	23756 KB	Output is correct
12	Correct	16 ms	23756 KB	Output is correct
13	Correct	15 ms	23712 KB	Output is correct
14	Correct	15 ms	23768 KB	Output is correct
15	Correct	14 ms	23820 KB	Output is correct
16	Correct	15 ms	23740 KB	Output is correct
17	Correct	15 ms	23756 KB	Output is correct
18	Correct	19 ms	23812 KB	Output is correct
19	Correct	15 ms	23756 KB	Output is correct
20	Correct	14 ms	23756 KB	Output is correct
21	Correct	15 ms	23756 KB	Output is correct
22	Correct	16 ms	23700 KB	Output is correct
23	Correct	15 ms	23808 KB	Output is correct
24	Correct	14 ms	23816 KB	Output is correct
25	Correct	15 ms	23792 KB	Output is correct
26	Correct	16 ms	23824 KB	Output is correct
27	Correct	17 ms	23756 KB	Output is correct
28	Correct	15 ms	23756 KB	Output is correct
29	Correct	14 ms	23756 KB	Output is correct
30	Correct	15 ms	23816 KB	Output is correct
31	Execution timed out	5024 ms	27020 KB	Time limit exceeded
32	Halted	0 ms	0 KB	-

Subtask #6
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	14 ms	23756 KB	Output is correct
2	Correct	14 ms	23760 KB	Output is correct
3	Correct	14 ms	23732 KB	Output is correct
4	Correct	14 ms	23740 KB	Output is correct
5	Correct	18 ms	23756 KB	Output is correct
6	Correct	17 ms	23796 KB	Output is correct
7	Correct	15 ms	23812 KB	Output is correct
8	Correct	15 ms	23740 KB	Output is correct
9	Correct	15 ms	23756 KB	Output is correct
10	Correct	15 ms	23740 KB	Output is correct
11	Correct	15 ms	23756 KB	Output is correct
12	Correct	16 ms	23756 KB	Output is correct
13	Correct	15 ms	23712 KB	Output is correct
14	Correct	15 ms	23768 KB	Output is correct
15	Correct	14 ms	23820 KB	Output is correct
16	Correct	15 ms	23740 KB	Output is correct
17	Correct	15 ms	23756 KB	Output is correct
18	Correct	19 ms	23812 KB	Output is correct
19	Correct	15 ms	23756 KB	Output is correct
20	Correct	14 ms	23756 KB	Output is correct
21	Correct	15 ms	23756 KB	Output is correct
22	Correct	16 ms	23700 KB	Output is correct
23	Correct	15 ms	23808 KB	Output is correct
24	Correct	14 ms	23816 KB	Output is correct
25	Correct	15 ms	23792 KB	Output is correct
26	Correct	16 ms	23824 KB	Output is correct
27	Correct	17 ms	23756 KB	Output is correct
28	Correct	15 ms	23756 KB	Output is correct
29	Correct	14 ms	23756 KB	Output is correct
30	Correct	15 ms	23816 KB	Output is correct
31	Execution timed out	5024 ms	27020 KB	Time limit exceeded
32	Halted	0 ms	0 KB	-

Submission #516787

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 0 / 7.0

Subtask #3 0 / 10.0

Subtask #4 0 / 23.0

Subtask #5 0 / 35.0

Subtask #6 0 / 20.0

Subtask #1
5.0 / 5.0

Subtask #2
0 / 7.0

Subtask #3
0 / 10.0

Subtask #4
0 / 23.0

Subtask #5
0 / 35.0

Subtask #6
0 / 20.0