Submission #49694

#	Time	Username	Problem	Language	Result	Execution time	Memory
49694		gs13105	New Home (APIO18_new_home)	C++17	57 / 100	5033 ms	408568 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;

static char buf[17100100]; // size : any number geq than 1024 
static int fio_idx = 0;
static int bytes = 0;
static inline int _read() {
    if(!bytes || fio_idx == bytes) {
        bytes = (int)fread(buf, sizeof(buf[0]), sizeof(buf), stdin);
        fio_idx = 0;
    }
    return buf[fio_idx++];
}
static inline int _readInt() {
    int x = 0;
    int c = _read();
    while(c <= 32) c = _read();
    while(c > 32) x = 10 * x + (c - '0'), c = _read();
    return x;
}

int n, k, q, bp;

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

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

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

list<eve> arr;
map<int, pos> loc[MAXN + 10];

struct seg
{
    int t1, t2, x, y;
    bool operator <(const seg &e) const
    {
        return x < e.x;
    }
};

list<seg> sor[2];
inline void add_seg(int t1, int t2, int x, int y)
{
    if(t1 > t2 || x == y)
        return;

    int nt1 = bp + idx(t1);
    int nt2 = bp + idx(t2 + 1) - 1;
    if(nt1 > nt2)
        return;

    if(y < x)
        sor[0].push_back({ nt1, nt2, y, x });
    else
        sor[1].push_back({ nt1, nt2, INF - y + 1, INF - x + 1 });
}

struct ent
{
    // v0 : dec, v1 : inc, q : query
    // v : { x, y }
    // q : { x, i }
    vector<pair<int, int>> v[2];
    vector<pair<int, int>> q;
};

ent mem[MAXI + 10];

struct que
{
    int l, y, i;
    bool operator <(const que &x) const
    {
        return l < x.l;
    }
};

list<que> inp;
bool chk[MAXN + 10];
int ans[MAXN + 10];

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

    n = _readInt();
    k = _readInt();
    q = _readInt();
    for(int i = 0; i < n; i++)
    {
        int x, t, a, b;
        x = _readInt();
        t = _readInt();
        a = _readInt();
        b = _readInt();
        arr.push_back({ a, x, t });
        arr.push_back({ b, x, -t });
    }
    for(int i = 0; i < q; i++)
    {
        int l, y;
        l = _readInt();
        y = _readInt();
        inp.push_back({ l, y, i });
        com.push_back(y);
    }

    sort(com.begin(), com.end());
    com.erase(unique(com.begin(), com.end()), com.end());

    int sz = com.size();
    for(bp = 1; bp < sz; bp *= 2);

    arr.sort();
    int cur, cnt = 0;
    for(eve &e : arr)
    {
        if(e.d > 0)
        {
            if(loc[e.d].size() == 0)
            {
                cnt++;
                if(cnt == k)
                    cur = e.t;
            }

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

            it = loc[e.d].insert({ e.x,{ 1, 1, e.t, INF, e.t } }).first;
            pos &p = it->second;

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

                add_seg(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) != loc[e.d].end())
            {
                int x = next(it)->first;
                pos &q = next(it)->second;

                add_seg(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 = loc[e.d].find(e.x);
            pos &p = it->second;

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

            add_seg(p.lt, e.t, e.x, p.l);
            add_seg(p.rt, e.t, e.x, p.r);

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

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

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

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

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

            if(loc[e.d].size() == 0)
            {
                if(cnt == k)
                {
                    int t1 = idx(cur);
                    int t2 = idx(e.t + 1) - 1;
                    for(int i = t1; i <= t2; i++)
                        chk[i] = 1;
                }
                cnt--;
            }
        }
    }

    inp.sort();
    for(que &e : inp)
    {
        int x = idx(e.y);
        if(chk[x])
        {
            x += bp;
            while(x)
            {
                mem[x].q.push_back({ e.l, e.i });
                x /= 2;
            }
        }
        else
            ans[e.i] = -1;
    }

    for(int i = 0; i < 2; i++)
    {
        sor[i].sort();
        for(seg &e : sor[i])
        {
            int t1 = e.t1;
            int t2 = e.t2;
            while(t1 < t2)
            {
                if(t1 % 2 == 1)
                {
                    mem[t1].v[i].push_back({ e.x, e.y });
                    t1++;
                }
                if(t2 % 2 == 0)
                {
                    mem[t2].v[i].push_back({ e.x, e.y });
                    t2--;
                }
                t1 /= 2;
                t2 /= 2;
            }
            if(t1 == t2)
                mem[t1].v[i].push_back({ e.x, e.y });
        }
    }

    for(int x = 1; x <= bp + sz - 1; x++)
    {
        {
            int mx, p1, p2, sz1, sz2;
            sz1 = mem[x].v[0].size();
            sz2 = mem[x].q.size();
            mx = p1 = p2 = 0;

            while(p2 < sz2)
            {
                if(p1 != sz1 && mem[x].v[0][p1].first <= mem[x].q[p2].first)
                {
                    mx = max(mx, mem[x].v[0][p1].second);
                    p1++;
                }
                else
                {
                    ans[mem[x].q[p2].second] = max(ans[mem[x].q[p2].second], mx - mem[x].q[p2].first);
                    p2++;
                }
            }
        }
        {
            int mx, p1, p2, sz1;
            sz1 = mem[x].v[1].size();
            mx = p1 = 0;
            p2 = mem[x].q.size() - 1;

            while(p2 >= 0)
            {
                int qx = INF - mem[x].q[p2].first + 1;
                if(p1 != sz1 && mem[x].v[1][p1].first <= qx)
                {
                    mx = max(mx, mem[x].v[1][p1].second);
                    p1++;
                }
                else
                {
                    ans[mem[x].q[p2].second] = max(ans[mem[x].q[p2].second], mx - qx);
                    p2--;
                }
            }
        }
    }

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

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