Submission #864564

#	Time	Username	Problem	Language	Result	Execution time	Memory
864564		danikoynov	New Home (APIO18_new_home)	C++14	5 / 100	2 ms	604 KiB

new_home

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

const int maxn = 410, inf = 1e9;

struct store
{
    int x, t, a, b;
}s[maxn];

struct query
{
    int l, y;
}task[maxn];

int n, k, q;

void input()
{
    cin >> n >> k >> q;
    for (int i = 1; i <= n; i ++)
        cin >> s[i].x >> s[i].t >> s[i].a >> s[i].b;

    for (int i = 1; i <= q; i ++)
        cin >> task[i].l >> task[i].y;
}

int type[maxn];
int solve_naive(int pivot, int year)
{
    for (int i = 1; i <= k; i ++)
        type[i] = inf;

    for (int i = 1; i <= n; i ++)
    {
        if (s[i].a <= year && s[i].b >= year)
            type[s[i].t] = min(type[s[i].t], abs(pivot - s[i].x));
    }

    int ans = -1;
    for (int i = 1; i <= k; i ++)
    {
        if (type[i] == inf)
            return -1;
        ans = max(ans, type[i]);
    }

    return ans;
}
void answer_queries()
{
    for (int i = 1; i <= q; i ++)
    {
        cout << solve_naive(task[i].l, task[i].y) << endl;
    }
}
void solve()
{
    input();
    answer_queries();
}

int main()
{
    solve();
    return 0;
}

/**
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

2 1 3
1 1 1 4
1 1 2 6
1 3
1 5
1 7

1 1 1
100000000 1 1 1
1 1



*/

• Subtask 1: 5 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 10
• Subtask 4: 0 / 23
• Subtask 5: 0 / 35
• Subtask 6: 0 / 20