Submission #864613

#	Time	Username	Problem	Language	Result	Execution time	Memory
864613		danikoynov	New Home (APIO18_new_home)	C++14	47 / 100	5089 ms	594408 KiB

new_home

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

const int maxn = 6e5 + 10, inf = 1e9;

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

struct query
{
    int l, y, idx;
}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, task[i].idx = i;
}

unordered_map < int, int > rev;
int dif, back_to[2 * maxn];

int get_mid(int left, int right)
{
    if (left == right)
        return rev[left];
    
    int lf = rev[left], rf = rev[right];
    while(lf <= rf)
    {
        int mf = (lf + rf) / 2;
        if (abs(left - back_to[mf]) <= abs(right - back_to[mf]))
            lf = mf + 1;
        else
            rf = mf - 1;
    }

    return rf;
}
void compress_data()
{
    vector < int > cor;
    for (int i = 1; i <= n; i ++)
        cor.push_back(s[i].x);
    for (int i = 1; i <= q; i ++)
        cor.push_back(task[i].l);

    sort(cor.begin(), cor.end());
    int sz = cor.size();

    for (int i = 0; i < cor.size(); i ++)
    {
        if (i != 0 || cor[i - 1] != cor[i])
        {
            dif ++;
            rev[cor[i]] = dif;
            back_to[dif] = cor[i];
        }
    }
}
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;
}

bool cmp_query(query t1, query t2)
{
    return t1.y < t2.y;
}

struct event
{
    int type, cor, add, arrive;

    event(int _type, int _cor, int _add, int _arrive)
    {
        type = _type;
        cor = _cor;
        add = _add;
        arrive = _arrive;
    }
};

bool cmp_event(event e1, event e2)
{
    if (e1.arrive != e2.arrive)
        return e1.arrive < e2.arrive;

    if (e1.add != e2.add)
        return e1.add < e2.add;

    return e1.cor < e2.cor; /// could have dublicates
}




multiset < int > tree[4 * maxn];

void apply_update(int root, pair < int, int > val)
{
    if (val.first == -1)
    {
        tree[root].erase(tree[root].find(val.second));
    }
    else
    {
        tree[root].insert(val.second);
    }
}

void update(int root, int left, int right, int qleft, int qright, pair < int, int > val)
{
    if (left > qright || right < qleft)
        return;

    if (left >= qleft && right <= qright)
    {
        apply_update(root, val);
        return;
    }

    int mid = (left + right) / 2;

    update(root * 2, left, mid, qleft, qright, val);
    update(root * 2 + 1, mid + 1, right, qleft, qright, val);
}

int query(int root, int left, int right, int pos, int cor)
{   
   
    int far = 0;
    if (!tree[root].empty())
    {
        far = max(far, abs(cor - *tree[root].begin()));
        far = max(far, abs(cor - *tree[root].rbegin()));
    }
    
    if (left != right)
    {
        int mid = (left + right) / 2;
        if (pos <= mid)
            far = max(far, query(root * 2, left, mid, pos, cor));
        else
            far = max(far, query(root * 2 + 1, mid + 1, right, pos, cor));
    }
        ///cout << root << " " << left << " " << right << " " << pos << " " << cor << endl;
        ///cout << far << " : " << cor<< endl; 

    return far;
}

multiset < int > act[maxn];

void add_event(int type, int cor)
{
    multiset < int > :: iterator it = act[type].upper_bound(cor);
    int aft = *it;
    int bef = *prev(it);

    if (bef == -inf && aft == inf)
    {
        update(1, 1, dif, 1, dif, {-1, -inf});
        update(1, 1, dif, 1, rev[cor], {1, cor});
        update(1, 1, dif, rev[cor], dif, {1, cor});
        ///cout << "from to " << rev[cor] << endl;
    }
    else
    if (bef == - inf) // aft != inf
    {
        update(1, 1, dif, 1, rev[aft], {-1, aft});
        update(1, 1, dif, 1, rev[cor], {1, cor});
        int mid = get_mid(cor, aft);
        update(1, 1, dif, rev[cor], mid, {1, cor});
        update(1, 1, dif, mid + 1, rev[aft], {1, aft});
    }
    else
    if (aft == inf) // bef != inf
    {
        update(1, 1, dif, rev[bef], dif, {-1, bef});
        update(1, 1, dif, rev[cor], dif, {1, cor});
        int mid = get_mid(bef, cor);
        ///cout << "here " << mid << endl;
        update(1, 1, dif, rev[bef], mid, {1, bef});
        update(1, 1, dif, mid + 1, rev[cor], {1, cor});
    }
    else   /// aft != inf && bef != inf
    {
        int mid = get_mid(bef, aft);
        update(1, 1, dif, rev[bef], mid, {-1, bef});
        update(1, 1, dif, mid + 1, rev[aft], {-1, aft});
        int mid_left = get_mid(bef, cor);
        update(1, 1, dif, rev[bef], mid_left, {1, bef});
        update(1, 1, dif, mid_left + 1, rev[cor], {1, cor});
        int mid_right = get_mid(cor, aft);
        update(1, 1, dif, rev[cor], mid_right, {1, cor});
        update(1, 1, dif, mid_right + 1, rev[aft], {1, aft});
    }

    act[type].insert(cor);
}

void remove_event(int type, int cor)
{
    multiset < int > :: iterator it = act[type].find(cor);
    int aft = *next(it);
    int bef = *prev(it);

    if (bef == -inf && aft == inf)
    {
        update(1, 1, dif, 1, dif, {+1, -inf});
        update(1, 1, dif, 1, rev[cor], {-1, cor});
        update(1, 1, dif, rev[cor], dif, {-1, cor});
    }
    else
    if (bef == - inf) // aft != inf
    {
        update(1, 1, dif, 1, rev[aft], {1, aft});
        update(1, 1, dif, 1, rev[cor], {-1, cor});
        int mid = get_mid(cor, aft);
        update(1, 1, dif, rev[cor], mid, {-1, cor});
        update(1, 1, dif, mid + 1, rev[aft], {-1, aft});
    }
    else
    if (aft == inf) // bef != inf
    {
        update(1, 1, dif, rev[bef], dif, {1, bef});
        update(1, 1, dif, rev[cor], dif, {-1, cor});
        int mid = get_mid(bef, cor);
        update(1, 1, dif, rev[bef], mid, {-1, bef});
        update(1, 1, dif, mid + 1, rev[cor], {-1, cor});
    }
    else   /// aft != inf && bef != inf
    {
        int mid = get_mid(bef, aft);
        update(1, 1, dif, rev[bef], mid, {1, bef});
        update(1, 1, dif, mid + 1, rev[aft], {1, aft});
        int mid_left = get_mid(bef, cor);
        update(1, 1, dif, rev[bef], mid_left, {-1, bef});
        update(1, 1, dif, mid_left + 1, rev[cor], {-1, cor});
        int mid_right = get_mid(cor, aft);
        update(1, 1, dif, rev[cor], mid_right, {-1, cor});
        update(1, 1, dif, mid_right + 1, rev[aft], {-1, aft});
    }

    act[type].erase(it);
}

int ans[maxn];

int single_query(int cor)
{
    /**int far = 0;
    for (int i = 1; i <= k; i ++)
    {
        multiset < int > :: iterator it = act[i].upper_bound(cor);
        int closest = inf;
        ///if (it != act[i].end())
        ///cout << "here " << cor << " " << *it << endl;
        if (it != act[i].end())
            closest = min(closest, *it - cor);
        
        if (it != act[i].begin())
            closest = min(closest, cor - *prev(it));
        
        far = max(far, closest);
        ///cout << far << endl;
    }*/

    int far = query(1, 1, dif, rev[cor], cor);

    if (far > 2e8)
        return -1;

    return far;
}

void answer_queries()
{
    sort(task + 1, task + q + 1, cmp_query);
    
    vector < event > events;
    for (int i = 1; i <= n; i ++)
    {
        events.push_back(event(s[i].t, s[i].x, 1, s[i].a));
        events.push_back(event(s[i].t, s[i].x, -1, s[i].b + 1));
    }

    sort(events.begin(), events.end(), cmp_event);

    for (int i = 1; i <= k; i ++)
    {
        act[i].insert(-inf);
        act[i].insert(inf);
        update(1, 1, dif, 1, dif, {1, -inf});
    }

    int pt = 1;
    for (event cur : events)
    {
        
        while(pt <= q && task[pt].y < cur.arrive)
        {
            ans[task[pt].idx] = single_query(task[pt].l);
            pt ++;
        }
        ///cout << "event " << cur.arrive << " " << cur.add << " " << cur.cor << endl;
        if (cur.add == 1)
            add_event(cur.type, cur.cor);
        else
            remove_event(cur.type, cur.cor);
    }

    while(pt <= q)
    {
         ans[task[pt].idx] = single_query(task[pt].l);
         pt ++;
    }

    for (int i = 1; i <= q; i ++)
        cout << ans[i] << endl;
}
void solve()
{
    input();
    compress_data();
    answer_queries();
}

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
int main()
{
    speed();
    solve();
    return 0;
}

/**
2 1 2
3 1 1 3
5 1 3 4
3 3
3 4




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



*/

Compilation message (stderr)

new_home.cpp: In function 'void compress_data()':
new_home.cpp:62:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |     for (int i = 0; i < cor.size(); i ++)
      |                     ~~^~~~~~~~~~~~
new_home.cpp:60:9: warning: unused variable 'sz' [-Wunused-variable]
   60 |     int sz = cor.size();
      |         ^~

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