답안 #49451 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
49451	2018-05-29T06:24:52 Z	gs13105	새 집 (APIO18_new_home)	C++17	5 / 100	5000 ms	306792 KB

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

// add  : t time, p = 1, [x -> y] loc, d origin
// query: t time, p = 2, x loc, y idx, d = -1
// sub  : t time, p = 3, [x -> y] loc, d origin
struct eve2
{
    int t, p, x, y, d;
    bool operator <(const eve2 &e) const
    {
        return t != e.t ? t < e.t : p < e.p;
    }
};

vector<eve2> arr2;
void add_seg(int t, int t2, int x, int y)
{
    if(t > t2 || x == y)
        return;

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

    arr2.push_back({ t, 1, nx, ny, x });
    arr2.push_back({ t2, 3, nx, ny, x });
}

multiset<int> mem2[MAXI + 10];

void add(const eve2 &e)
{
    int x = e.x;
    int y = e.y;

    while(x < y)
    {
        if(x % 2 == 1)
        {
            if(e.p == 1)
                mem2[x].insert(e.d);
            else
                mem2[x].erase(mem2[x].find(e.d));
            x++;
        }
        if(y % 2 == 0)
        {
            if(e.p == 1)
                mem2[y].insert(e.d);
            else
                mem2[y].erase(mem2[y].find(e.d));
            y--;
        }
        x /= 2;
        y /= 2;
    }
    if(x == y)
    {
        if(e.p == 1)
            mem2[x].insert(e.d);
        else
            mem2[x].erase(mem2[x].find(e.d));
    }
}

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

    while(x)
    {
        for(int t : mem2[x])
            r = max(r, abs(t - p));
        /*
        auto it = mem2[x].lower_bound(p);
        if(it != mem2[x].end())
            r = max(r, *it - p);
        if(it != mem2[x].begin())
            r = max(r, p - *prev(it));
        */
        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, 2, l, i, -1 });
        com.push_back(l);
    }

    sort(com.begin(), com.end());
    com.erase(unique(com.begin(), com.end()), com.end());
    for(bp = 1; bp < (int)com.size(); 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;

                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) != loc1[e.d].end())
            {
                int x = next(it)->first;
                ent1 &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 = loc1[e.d].find(e.x);
            ent1 &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 != loc1[e.d].begin())
            {
                int x = prev(it)->first;
                ent1 &q = prev(it)->second;

                add_seg(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;

                add_seg(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.p == 1 || e.p == 3)
            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.x);
            else
                ans[e.y] = -1;
        }
    }

    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:142: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:146: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:153: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.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	57 ms	63608 KB	Output is correct
2	Correct	66 ms	63660 KB	Output is correct
3	Correct	55 ms	63664 KB	Output is correct
4	Correct	54 ms	63792 KB	Output is correct
5	Correct	58 ms	63828 KB	Output is correct
6	Correct	59 ms	64048 KB	Output is correct
7	Correct	58 ms	64048 KB	Output is correct
8	Correct	55 ms	64092 KB	Output is correct
9	Correct	53 ms	64092 KB	Output is correct
10	Correct	55 ms	64092 KB	Output is correct
11	Correct	54 ms	64092 KB	Output is correct
12	Correct	57 ms	64092 KB	Output is correct
13	Correct	53 ms	64092 KB	Output is correct
14	Correct	62 ms	64092 KB	Output is correct
15	Correct	60 ms	64092 KB	Output is correct
16	Correct	66 ms	64092 KB	Output is correct
17	Correct	66 ms	64108 KB	Output is correct
18	Correct	57 ms	64108 KB	Output is correct
19	Correct	58 ms	64112 KB	Output is correct
20	Correct	77 ms	64112 KB	Output is correct
21	Correct	56 ms	64112 KB	Output is correct
22	Correct	63 ms	64112 KB	Output is correct
23	Correct	55 ms	64112 KB	Output is correct
24	Correct	61 ms	64112 KB	Output is correct
25	Correct	55 ms	64124 KB	Output is correct
26	Correct	54 ms	64124 KB	Output is correct
27	Correct	54 ms	64124 KB	Output is correct
28	Correct	62 ms	64124 KB	Output is correct
29	Correct	52 ms	64124 KB	Output is correct
30	Correct	55 ms	64124 KB	Output is correct

Subtask #2
0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	57 ms	63608 KB	Output is correct
2	Correct	66 ms	63660 KB	Output is correct
3	Correct	55 ms	63664 KB	Output is correct
4	Correct	54 ms	63792 KB	Output is correct
5	Correct	58 ms	63828 KB	Output is correct
6	Correct	59 ms	64048 KB	Output is correct
7	Correct	58 ms	64048 KB	Output is correct
8	Correct	55 ms	64092 KB	Output is correct
9	Correct	53 ms	64092 KB	Output is correct
10	Correct	55 ms	64092 KB	Output is correct
11	Correct	54 ms	64092 KB	Output is correct
12	Correct	57 ms	64092 KB	Output is correct
13	Correct	53 ms	64092 KB	Output is correct
14	Correct	62 ms	64092 KB	Output is correct
15	Correct	60 ms	64092 KB	Output is correct
16	Correct	66 ms	64092 KB	Output is correct
17	Correct	66 ms	64108 KB	Output is correct
18	Correct	57 ms	64108 KB	Output is correct
19	Correct	58 ms	64112 KB	Output is correct
20	Correct	77 ms	64112 KB	Output is correct
21	Correct	56 ms	64112 KB	Output is correct
22	Correct	63 ms	64112 KB	Output is correct
23	Correct	55 ms	64112 KB	Output is correct
24	Correct	61 ms	64112 KB	Output is correct
25	Correct	55 ms	64124 KB	Output is correct
26	Correct	54 ms	64124 KB	Output is correct
27	Correct	54 ms	64124 KB	Output is correct
28	Correct	62 ms	64124 KB	Output is correct
29	Correct	52 ms	64124 KB	Output is correct
30	Correct	55 ms	64124 KB	Output is correct
31	Execution timed out	5086 ms	118936 KB	Time limit exceeded
32	Halted	0 ms	0 KB	-

Subtask #3
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	5068 ms	306792 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #4
0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	5108 ms	306792 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #5
0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	57 ms	63608 KB	Output is correct
2	Correct	66 ms	63660 KB	Output is correct
3	Correct	55 ms	63664 KB	Output is correct
4	Correct	54 ms	63792 KB	Output is correct
5	Correct	58 ms	63828 KB	Output is correct
6	Correct	59 ms	64048 KB	Output is correct
7	Correct	58 ms	64048 KB	Output is correct
8	Correct	55 ms	64092 KB	Output is correct
9	Correct	53 ms	64092 KB	Output is correct
10	Correct	55 ms	64092 KB	Output is correct
11	Correct	54 ms	64092 KB	Output is correct
12	Correct	57 ms	64092 KB	Output is correct
13	Correct	53 ms	64092 KB	Output is correct
14	Correct	62 ms	64092 KB	Output is correct
15	Correct	60 ms	64092 KB	Output is correct
16	Correct	66 ms	64092 KB	Output is correct
17	Correct	66 ms	64108 KB	Output is correct
18	Correct	57 ms	64108 KB	Output is correct
19	Correct	58 ms	64112 KB	Output is correct
20	Correct	77 ms	64112 KB	Output is correct
21	Correct	56 ms	64112 KB	Output is correct
22	Correct	63 ms	64112 KB	Output is correct
23	Correct	55 ms	64112 KB	Output is correct
24	Correct	61 ms	64112 KB	Output is correct
25	Correct	55 ms	64124 KB	Output is correct
26	Correct	54 ms	64124 KB	Output is correct
27	Correct	54 ms	64124 KB	Output is correct
28	Correct	62 ms	64124 KB	Output is correct
29	Correct	52 ms	64124 KB	Output is correct
30	Correct	55 ms	64124 KB	Output is correct
31	Execution timed out	5086 ms	118936 KB	Time limit exceeded
32	Halted	0 ms	0 KB	-

Subtask #6
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	57 ms	63608 KB	Output is correct
2	Correct	66 ms	63660 KB	Output is correct
3	Correct	55 ms	63664 KB	Output is correct
4	Correct	54 ms	63792 KB	Output is correct
5	Correct	58 ms	63828 KB	Output is correct
6	Correct	59 ms	64048 KB	Output is correct
7	Correct	58 ms	64048 KB	Output is correct
8	Correct	55 ms	64092 KB	Output is correct
9	Correct	53 ms	64092 KB	Output is correct
10	Correct	55 ms	64092 KB	Output is correct
11	Correct	54 ms	64092 KB	Output is correct
12	Correct	57 ms	64092 KB	Output is correct
13	Correct	53 ms	64092 KB	Output is correct
14	Correct	62 ms	64092 KB	Output is correct
15	Correct	60 ms	64092 KB	Output is correct
16	Correct	66 ms	64092 KB	Output is correct
17	Correct	66 ms	64108 KB	Output is correct
18	Correct	57 ms	64108 KB	Output is correct
19	Correct	58 ms	64112 KB	Output is correct
20	Correct	77 ms	64112 KB	Output is correct
21	Correct	56 ms	64112 KB	Output is correct
22	Correct	63 ms	64112 KB	Output is correct
23	Correct	55 ms	64112 KB	Output is correct
24	Correct	61 ms	64112 KB	Output is correct
25	Correct	55 ms	64124 KB	Output is correct
26	Correct	54 ms	64124 KB	Output is correct
27	Correct	54 ms	64124 KB	Output is correct
28	Correct	62 ms	64124 KB	Output is correct
29	Correct	52 ms	64124 KB	Output is correct
30	Correct	55 ms	64124 KB	Output is correct
31	Execution timed out	5086 ms	118936 KB	Time limit exceeded
32	Halted	0 ms	0 KB	-

답안 #49451

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 0 / 7.0

Subtask #3 0 / 10.0

Subtask #4 0 / 23.0

Subtask #5 0 / 35.0

Subtask #6 0 / 20.0

Subtask #1
5.0 / 5.0

Subtask #2
0 / 7.0

Subtask #3
0 / 10.0

Subtask #4
0 / 23.0

Subtask #5
0 / 35.0

Subtask #6
0 / 20.0