답안 #49723 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
49723	2018-06-02T10:26:46 Z	gs13105	새 집 (APIO18_new_home)	C++17	57 / 100	5000 ms	365324 KB

new_home

//#pragma GCC optimize ("O3")

#include <cstdio>
#include <cassert>
#include <algorithm>
#include <vector>
#include <map>
#include <iterator>

using namespace std;

#define INF 100000000

static char buf[33554432];
static int fio_idx = 0;
static inline int _readInt() {
    int x = 0;
    int c = buf[fio_idx++];
    if(c <= 32) c = buf[fio_idx++];
    while(c > 32) x = 10 * x + (c - '0'), c = buf[fio_idx++];
    return x;
}

int n, k, q, bp;

int com[524288];
int c_sz;
inline int idx(int x)
{
    return lower_bound(com, com + c_sz, x) - com;
}

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;
};

eve arr[1048576];
map<int, pos> loc[524288];

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

seg sor0[1048576];
seg sor1[1048576];
int s_sz0, s_sz1;
inline void add_seg(const int &t1, const int &t2, const int &x, const 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)
        sor0[s_sz0++] = { nt1, nt2, y, x };
    else
        sor1[s_sz1++] = { nt1, nt2, -y, -x };
}

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

ent mem[1048576];

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

que inp[524288];
bool chk[524288];
int ans[524288];

int main()
{
    fread(buf, sizeof(buf[0]), sizeof(buf), stdin);
    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[2 * i] = { a, x, t };
        arr[2 * i + 1] = { b, x, -t };
    }
    for(int i = 0; i < q; i++)
    {
        int l, y;
        l = _readInt();
        y = _readInt();
        inp[i] = { l, y, i };
        com[i] = y;
    }

    sort(com, com + q);
    c_sz = unique(com, com + q) - com;

    for(bp = 1; bp < c_sz; bp *= 2);

    sort(arr, arr + 2 * n);
    int cur, cnt = 0;
    for(int u = 0; u < 2 * n; u++)
    {
        eve &e = arr[u];
        if(e.d > 0)
        {
            if(loc[e.d].empty())
            {
                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())
            {
                auto it2 = prev(it);
                int x = it2->first;
                pos &q = it2->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;
            }

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

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

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

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

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

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

            if(loc[e.d].empty())
            {
                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--;
            }
        }
    }

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

    {
        sort(sor0, sor0 + s_sz0);
        for(int u = 0; u < s_sz0; u++)
        {
            seg &e = sor0[u];
            while(e.t1 < e.t2)
            {
                if(e.t1 % 2 == 1)
                {
                    mem[e.t1].v0.push_back({ e.x, e.y });
                    e.t1++;
                }
                if(e.t2 % 2 == 0)
                {
                    mem[e.t2].v0.push_back({ e.x, e.y });
                    e.t2--;
                }
                e.t1 /= 2;
                e.t2 /= 2;
            }
            if(e.t1 == e.t2)
                mem[e.t1].v0.push_back({ e.x, e.y });
        }
    }
    {
        sort(sor1, sor1 + s_sz1);
        for(int u = 0; u < s_sz1; u++)
        {
            seg &e = sor1[u];
            while(e.t1 < e.t2)
            {
                if(e.t1 % 2 == 1)
                {
                    mem[e.t1].v1.push_back({ e.x, e.y });
                    e.t1++;
                }
                if(e.t2 % 2 == 0)
                {
                    mem[e.t2].v1.push_back({ e.x, e.y });
                    e.t2--;
                }
                e.t1 /= 2;
                e.t2 /= 2;
            }
            if(e.t1 == e.t2)
                mem[e.t1].v1.push_back({ e.x, e.y });
        }
    }

    for(int x = 1; x <= bp + c_sz - 1; x++)
    {
        if(mem[x].q.empty())
            continue;

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

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

Compilation message

new_home.cpp: In function 'int main()':
new_home.cpp:324:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while(p2 < mem[x].q.size())
                   ~~~^~~~~~~~~~~~~~~~~
new_home.cpp:326:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 if(p1 != mem[x].v0.size() && mem[x].v0[p1].first <= mem[x].q[p2].first)
                    ~~~^~~~~~~~~~~~~~~~~~~
new_home.cpp:345:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 if(p1 != mem[x].v1.size() && mem[x].v1[p1].first <= -mem[x].q[p2].first)
                    ~~~^~~~~~~~~~~~~~~~~~~
new_home.cpp:104:10: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     fread(buf, sizeof(buf[0]), sizeof(buf), stdin);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	83 ms	98808 KB	Output is correct
2	Correct	81 ms	98920 KB	Output is correct
3	Correct	82 ms	98920 KB	Output is correct
4	Correct	94 ms	98996 KB	Output is correct
5	Correct	86 ms	99156 KB	Output is correct
6	Correct	83 ms	99232 KB	Output is correct
7	Correct	96 ms	99232 KB	Output is correct
8	Correct	84 ms	99232 KB	Output is correct
9	Correct	88 ms	99256 KB	Output is correct
10	Correct	89 ms	99524 KB	Output is correct
11	Correct	84 ms	99524 KB	Output is correct
12	Correct	86 ms	99524 KB	Output is correct
13	Correct	84 ms	99524 KB	Output is correct
14	Correct	86 ms	99524 KB	Output is correct
15	Correct	84 ms	99524 KB	Output is correct
16	Correct	87 ms	99524 KB	Output is correct
17	Correct	90 ms	99524 KB	Output is correct
18	Correct	87 ms	99524 KB	Output is correct
19	Correct	86 ms	99524 KB	Output is correct
20	Correct	86 ms	99524 KB	Output is correct
21	Correct	84 ms	99524 KB	Output is correct
22	Correct	134 ms	99524 KB	Output is correct
23	Correct	86 ms	99524 KB	Output is correct
24	Correct	85 ms	99524 KB	Output is correct
25	Correct	82 ms	99524 KB	Output is correct
26	Correct	83 ms	99524 KB	Output is correct
27	Correct	78 ms	99524 KB	Output is correct
28	Correct	81 ms	99524 KB	Output is correct
29	Correct	84 ms	99524 KB	Output is correct
30	Correct	85 ms	99524 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	83 ms	98808 KB	Output is correct
2	Correct	81 ms	98920 KB	Output is correct
3	Correct	82 ms	98920 KB	Output is correct
4	Correct	94 ms	98996 KB	Output is correct
5	Correct	86 ms	99156 KB	Output is correct
6	Correct	83 ms	99232 KB	Output is correct
7	Correct	96 ms	99232 KB	Output is correct
8	Correct	84 ms	99232 KB	Output is correct
9	Correct	88 ms	99256 KB	Output is correct
10	Correct	89 ms	99524 KB	Output is correct
11	Correct	84 ms	99524 KB	Output is correct
12	Correct	86 ms	99524 KB	Output is correct
13	Correct	84 ms	99524 KB	Output is correct
14	Correct	86 ms	99524 KB	Output is correct
15	Correct	84 ms	99524 KB	Output is correct
16	Correct	87 ms	99524 KB	Output is correct
17	Correct	90 ms	99524 KB	Output is correct
18	Correct	87 ms	99524 KB	Output is correct
19	Correct	86 ms	99524 KB	Output is correct
20	Correct	86 ms	99524 KB	Output is correct
21	Correct	84 ms	99524 KB	Output is correct
22	Correct	134 ms	99524 KB	Output is correct
23	Correct	86 ms	99524 KB	Output is correct
24	Correct	85 ms	99524 KB	Output is correct
25	Correct	82 ms	99524 KB	Output is correct
26	Correct	83 ms	99524 KB	Output is correct
27	Correct	78 ms	99524 KB	Output is correct
28	Correct	81 ms	99524 KB	Output is correct
29	Correct	84 ms	99524 KB	Output is correct
30	Correct	85 ms	99524 KB	Output is correct
31	Correct	960 ms	168760 KB	Output is correct
32	Correct	115 ms	168760 KB	Output is correct
33	Correct	978 ms	168760 KB	Output is correct
34	Correct	943 ms	168760 KB	Output is correct
35	Correct	1018 ms	169788 KB	Output is correct
36	Correct	986 ms	169808 KB	Output is correct
37	Correct	641 ms	169808 KB	Output is correct
38	Correct	633 ms	169808 KB	Output is correct
39	Correct	498 ms	169808 KB	Output is correct
40	Correct	544 ms	169808 KB	Output is correct
41	Correct	691 ms	169808 KB	Output is correct
42	Correct	599 ms	169808 KB	Output is correct
43	Correct	107 ms	169808 KB	Output is correct
44	Correct	589 ms	169808 KB	Output is correct
45	Correct	552 ms	169808 KB	Output is correct
46	Correct	448 ms	169808 KB	Output is correct
47	Correct	290 ms	169808 KB	Output is correct
48	Correct	274 ms	169808 KB	Output is correct
49	Correct	341 ms	169808 KB	Output is correct
50	Correct	380 ms	169808 KB	Output is correct
51	Correct	441 ms	169808 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1513 ms	252108 KB	Output is correct
2	Correct	1909 ms	253680 KB	Output is correct
3	Correct	1708 ms	253680 KB	Output is correct
4	Correct	1656 ms	253680 KB	Output is correct
5	Correct	2220 ms	273480 KB	Output is correct
6	Correct	1744 ms	273480 KB	Output is correct
7	Correct	1632 ms	273480 KB	Output is correct
8	Correct	1525 ms	273480 KB	Output is correct
9	Correct	1754 ms	276788 KB	Output is correct
10	Correct	1632 ms	276788 KB	Output is correct
11	Correct	1068 ms	276788 KB	Output is correct
12	Correct	1113 ms	276788 KB	Output is correct

Subtask #4
0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4805 ms	344744 KB	Output is correct
2	Correct	243 ms	344744 KB	Output is correct
3	Correct	4870 ms	365324 KB	Output is correct
4	Correct	990 ms	365324 KB	Output is correct
5	Correct	2533 ms	365324 KB	Output is correct
6	Correct	2203 ms	365324 KB	Output is correct
7	Execution timed out	5034 ms	365324 KB	Time limit exceeded
8	Halted	0 ms	0 KB	-

Subtask #5
35.0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	83 ms	98808 KB	Output is correct
2	Correct	81 ms	98920 KB	Output is correct
3	Correct	82 ms	98920 KB	Output is correct
4	Correct	94 ms	98996 KB	Output is correct
5	Correct	86 ms	99156 KB	Output is correct
6	Correct	83 ms	99232 KB	Output is correct
7	Correct	96 ms	99232 KB	Output is correct
8	Correct	84 ms	99232 KB	Output is correct
9	Correct	88 ms	99256 KB	Output is correct
10	Correct	89 ms	99524 KB	Output is correct
11	Correct	84 ms	99524 KB	Output is correct
12	Correct	86 ms	99524 KB	Output is correct
13	Correct	84 ms	99524 KB	Output is correct
14	Correct	86 ms	99524 KB	Output is correct
15	Correct	84 ms	99524 KB	Output is correct
16	Correct	87 ms	99524 KB	Output is correct
17	Correct	90 ms	99524 KB	Output is correct
18	Correct	87 ms	99524 KB	Output is correct
19	Correct	86 ms	99524 KB	Output is correct
20	Correct	86 ms	99524 KB	Output is correct
21	Correct	84 ms	99524 KB	Output is correct
22	Correct	134 ms	99524 KB	Output is correct
23	Correct	86 ms	99524 KB	Output is correct
24	Correct	85 ms	99524 KB	Output is correct
25	Correct	82 ms	99524 KB	Output is correct
26	Correct	83 ms	99524 KB	Output is correct
27	Correct	78 ms	99524 KB	Output is correct
28	Correct	81 ms	99524 KB	Output is correct
29	Correct	84 ms	99524 KB	Output is correct
30	Correct	85 ms	99524 KB	Output is correct
31	Correct	960 ms	168760 KB	Output is correct
32	Correct	115 ms	168760 KB	Output is correct
33	Correct	978 ms	168760 KB	Output is correct
34	Correct	943 ms	168760 KB	Output is correct
35	Correct	1018 ms	169788 KB	Output is correct
36	Correct	986 ms	169808 KB	Output is correct
37	Correct	641 ms	169808 KB	Output is correct
38	Correct	633 ms	169808 KB	Output is correct
39	Correct	498 ms	169808 KB	Output is correct
40	Correct	544 ms	169808 KB	Output is correct
41	Correct	691 ms	169808 KB	Output is correct
42	Correct	599 ms	169808 KB	Output is correct
43	Correct	107 ms	169808 KB	Output is correct
44	Correct	589 ms	169808 KB	Output is correct
45	Correct	552 ms	169808 KB	Output is correct
46	Correct	448 ms	169808 KB	Output is correct
47	Correct	290 ms	169808 KB	Output is correct
48	Correct	274 ms	169808 KB	Output is correct
49	Correct	341 ms	169808 KB	Output is correct
50	Correct	380 ms	169808 KB	Output is correct
51	Correct	441 ms	169808 KB	Output is correct
52	Correct	329 ms	365324 KB	Output is correct
53	Correct	334 ms	365324 KB	Output is correct
54	Correct	686 ms	365324 KB	Output is correct
55	Correct	579 ms	365324 KB	Output is correct
56	Correct	532 ms	365324 KB	Output is correct
57	Correct	638 ms	365324 KB	Output is correct
58	Correct	584 ms	365324 KB	Output is correct
59	Correct	488 ms	365324 KB	Output is correct
60	Correct	597 ms	365324 KB	Output is correct
61	Correct	132 ms	365324 KB	Output is correct
62	Correct	355 ms	365324 KB	Output is correct
63	Correct	489 ms	365324 KB	Output is correct
64	Correct	583 ms	365324 KB	Output is correct
65	Correct	680 ms	365324 KB	Output is correct
66	Correct	656 ms	365324 KB	Output is correct
67	Correct	177 ms	365324 KB	Output is correct

Subtask #6
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	83 ms	98808 KB	Output is correct
2	Correct	81 ms	98920 KB	Output is correct
3	Correct	82 ms	98920 KB	Output is correct
4	Correct	94 ms	98996 KB	Output is correct
5	Correct	86 ms	99156 KB	Output is correct
6	Correct	83 ms	99232 KB	Output is correct
7	Correct	96 ms	99232 KB	Output is correct
8	Correct	84 ms	99232 KB	Output is correct
9	Correct	88 ms	99256 KB	Output is correct
10	Correct	89 ms	99524 KB	Output is correct
11	Correct	84 ms	99524 KB	Output is correct
12	Correct	86 ms	99524 KB	Output is correct
13	Correct	84 ms	99524 KB	Output is correct
14	Correct	86 ms	99524 KB	Output is correct
15	Correct	84 ms	99524 KB	Output is correct
16	Correct	87 ms	99524 KB	Output is correct
17	Correct	90 ms	99524 KB	Output is correct
18	Correct	87 ms	99524 KB	Output is correct
19	Correct	86 ms	99524 KB	Output is correct
20	Correct	86 ms	99524 KB	Output is correct
21	Correct	84 ms	99524 KB	Output is correct
22	Correct	134 ms	99524 KB	Output is correct
23	Correct	86 ms	99524 KB	Output is correct
24	Correct	85 ms	99524 KB	Output is correct
25	Correct	82 ms	99524 KB	Output is correct
26	Correct	83 ms	99524 KB	Output is correct
27	Correct	78 ms	99524 KB	Output is correct
28	Correct	81 ms	99524 KB	Output is correct
29	Correct	84 ms	99524 KB	Output is correct
30	Correct	85 ms	99524 KB	Output is correct
31	Correct	960 ms	168760 KB	Output is correct
32	Correct	115 ms	168760 KB	Output is correct
33	Correct	978 ms	168760 KB	Output is correct
34	Correct	943 ms	168760 KB	Output is correct
35	Correct	1018 ms	169788 KB	Output is correct
36	Correct	986 ms	169808 KB	Output is correct
37	Correct	641 ms	169808 KB	Output is correct
38	Correct	633 ms	169808 KB	Output is correct
39	Correct	498 ms	169808 KB	Output is correct
40	Correct	544 ms	169808 KB	Output is correct
41	Correct	691 ms	169808 KB	Output is correct
42	Correct	599 ms	169808 KB	Output is correct
43	Correct	107 ms	169808 KB	Output is correct
44	Correct	589 ms	169808 KB	Output is correct
45	Correct	552 ms	169808 KB	Output is correct
46	Correct	448 ms	169808 KB	Output is correct
47	Correct	290 ms	169808 KB	Output is correct
48	Correct	274 ms	169808 KB	Output is correct
49	Correct	341 ms	169808 KB	Output is correct
50	Correct	380 ms	169808 KB	Output is correct
51	Correct	441 ms	169808 KB	Output is correct
52	Correct	1513 ms	252108 KB	Output is correct
53	Correct	1909 ms	253680 KB	Output is correct
54	Correct	1708 ms	253680 KB	Output is correct
55	Correct	1656 ms	253680 KB	Output is correct
56	Correct	2220 ms	273480 KB	Output is correct
57	Correct	1744 ms	273480 KB	Output is correct
58	Correct	1632 ms	273480 KB	Output is correct
59	Correct	1525 ms	273480 KB	Output is correct
60	Correct	1754 ms	276788 KB	Output is correct
61	Correct	1632 ms	276788 KB	Output is correct
62	Correct	1068 ms	276788 KB	Output is correct
63	Correct	1113 ms	276788 KB	Output is correct
64	Correct	4805 ms	344744 KB	Output is correct
65	Correct	243 ms	344744 KB	Output is correct
66	Correct	4870 ms	365324 KB	Output is correct
67	Correct	990 ms	365324 KB	Output is correct
68	Correct	2533 ms	365324 KB	Output is correct
69	Correct	2203 ms	365324 KB	Output is correct
70	Execution timed out	5034 ms	365324 KB	Time limit exceeded
71	Halted	0 ms	0 KB	-

답안 #49723

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 7.0 / 7.0

Subtask #3 10.0 / 10.0

Subtask #4 0 / 23.0

Subtask #5 35.0 / 35.0

Subtask #6 0 / 20.0

Subtask #1
5.0 / 5.0

Subtask #2
7.0 / 7.0

Subtask #3
10.0 / 10.0

Subtask #4
0 / 23.0

Subtask #5
35.0 / 35.0

Subtask #6
0 / 20.0