Submission #49448

#	Time	Username	Problem	Language	Result	Execution time	Memory
49448		gs13105	New Home (APIO18_new_home)	C++17	12 / 100	5117 ms	212992 KiB

new_home

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <tuple>
#include <iterator>

using namespace std;

const int MAXN = 300000;
const int MAXI = 1048576;
const int INF = 100000000;

int n, k, q, bp;

vector<int> com;
inline int idx(int x)
{
    return lower_bound(com.begin(), com.end(), x) - com.begin();
}

struct eve1
{
    int t, x, d;
    bool operator <(const eve1 &e) const
    {
        return t != e.t ? t < e.t : d > e.d;
    }
};

struct ent1
{
    int c, l, lt, r, rt;
};

vector<eve1> arr1;
map<int, ent1> loc1[MAXN + 10];

// segment: [t, t2] time, [x -> y] loc
// query  : t time, t2 = -1, x loc, y idx
struct eve2
{
    int t, t2, x, y;
    bool operator <(const eve2 &e) const
    {
        return t != e.t ? t < e.t : t2 > e.t2;
    }
};

struct ent2
{
    // list<pair<int, int>> a;
    // list<pair<int, int>> b;
    vector<pair<int, int>> a;
    vector<pair<int, int>> b;
};

vector<eve2> arr2;
ent2 mem2[MAXI + 10];

void upd(int x, int t, int v, int v2)
{
    if(v < v2)
        mem2[x].a.push_back({ v, t });
    else
        mem2[x].b.push_back({ v, t });
}

void add(const eve2 &e)
{
    if(e.t > e.t2 || e.x == e.y)
        return;

    int x = bp + idx(min(e.x, e.y));
    int y = bp + idx(max(e.x, e.y) + 1) - 1;
    if(x > y)
        return;

    while(x < y)
    {
        if(x % 2 == 1)
        {
            upd(x, e.t2, e.x, e.y);
            x++;
        }
        if(y % 2 == 0)
        {
            upd(y, e.t2, e.x, e.y);
            y--;
        }
        x /= 2;
        y /= 2;
    }
    if(x == y)
        upd(x, e.t2, e.x, e.y);
}

int get(int t, int p)
{
    int r = 0;
    int x = bp + idx(p);

    while(x)
    {
        for(auto &e : mem2[x].a)
            if(t <= e.second)
                r = max(r, abs(p - e.first));
        for(auto &e : mem2[x].b)
            if(t <= e.second)
                r = max(r, abs(p - e.first));
        x /= 2;
    }
    return r;
}

vector<pair<int, int>> can;
int ans[MAXN + 10];

int main()
{
    //freopen("in", "r", stdin);
    //freopen("out", "w", stdout);

    scanf("%d%d%d", &n, &k, &q);
    for(int i = 0; i < n; i++)
    {
        int x, t, a, b;
        scanf("%d%d%d%d", &x, &t, &a, &b);
        arr1.push_back({ a, x, t });
        arr1.push_back({ b, x, -t });
    }
    for(int i = 0; i < q; i++)
    {
        int l, y;
        scanf("%d%d", &l, &y);
        arr2.push_back({ y, -1, l, i });
        com.push_back(l);
    }

    sort(com.begin(), com.end());
    com.erase(unique(com.begin(), com.end()), com.end());
    int isz = (int)com.size();
    for(bp = 1; bp < isz; bp *= 2);

    sort(arr1.begin(), arr1.end());
    int cur, cnt = 0;
    for(eve1 &e : arr1)
    {
        if(e.d > 0)
        {
            if(loc1[e.d].size() == 0)
            {
                cnt++;
                if(cnt == k)
                    cur = e.t;
            }

            auto it = loc1[e.d].find(e.x);
            if(it != loc1[e.d].end())
            {
                it->second.c++;
                continue;
            }

            it = loc1[e.d].insert({ e.x, { 1, 1, e.t, INF, e.t } }).first;
            ent1 &p = it->second;
            
            if(it != loc1[e.d].begin())
            {
                int x = prev(it)->first;
                ent1 &q = prev(it)->second;

                arr2.push_back({ q.rt, e.t - 1, x, q.r });
                q.rt = e.t;
                q.r = (x + e.x) / 2;

                p.l = (x + e.x + 1) / 2;
            }

            if(next(it) != loc1[e.d].end())
            {
                int x = next(it)->first;
                ent1 &q = next(it)->second;

                arr2.push_back({ q.lt, e.t - 1, x, q.l });
                q.lt = e.t;
                q.l = (x + e.x + 1) / 2;

                p.r = (x + e.x) / 2;
            }
        }
        else
        {
            e.d = -e.d;

            auto it = loc1[e.d].find(e.x);
            ent1 &p = it->second;

            if(p.c > 1)
            {
                p.c--;
                continue;
            }

            arr2.push_back({ p.lt, e.t, e.x, p.l });
            arr2.push_back({ p.rt, e.t, e.x, p.r });

            if(it != loc1[e.d].begin())
            {
                int x = prev(it)->first;
                ent1 &q = prev(it)->second;

                arr2.push_back({ q.rt, e.t, x, q.r });
                q.rt = e.t + 1;
                if(next(it) != loc1[e.d].end())
                {
                    int y = next(it)->first;
                    q.r = (x + y) / 2;
                }
                else
                    q.r = INF;
            }

            if(next(it) != loc1[e.d].end())
            {
                int x = next(it)->first;
                ent1 &q = next(it)->second;

                arr2.push_back({ q.lt, e.t, x, q.l });
                q.lt = e.t + 1;
                if(it != loc1[e.d].begin())
                {
                    int y = prev(it)->first;
                    q.l = (y + x + 1) / 2;
                }
                else
                    q.l = 1;
            }

            loc1[e.d].erase(it);

            if(loc1[e.d].size() == 0)
            {
                if(cnt == k)
                    can.push_back({ cur, e.t });
                cnt--;
            }
        }
    }

    sort(arr2.begin(), arr2.end());
    int p = 0, sz = (int)can.size();
    for(eve2 &e : arr2)
    {
        if(e.t2 != -1)
            add(e);
        else
        {
            while(p < sz && can[p].second < e.t)
                p++;
            
            if(p < sz && can[p].first <= e.t)
                ans[e.y] = get(e.t, e.x);
            else
                ans[e.y] = -1;
        }
    }

    for(int i = 0; i < q; i++)
        printf("%d\n", ans[i]);
    return 0; 
}

Compilation message (stderr)

new_home.cpp: In function 'int main()':
new_home.cpp:134:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &n, &k, &q);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:138:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d%d", &x, &t, &a, &b);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:145:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &l, &y);
         ~~~~~^~~~~~~~~~~~~~~~

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