답안 #49705 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
49705	2018-06-02T09:07:11 Z	SpaimaCarpatilor	새 집 (APIO18_new_home)	C++17	57 / 100	5000 ms	147140 KB

new_home

#include<bits/stdc++.h>

using namespace std;

int N, K, Q, timeCount, xCount, x[300009], type[300009], a[300009], b[300009], location[300009], when[300009], ans[300009], realX[300009];
const int INF = 5e8;
int changesLine = 0;
vector < pair < int*, int > > changes[40];
multiset < int > S[300009];
vector < pair < int, int > > setChanges[40];

void update (int &x, int y)
{
    if (y > x)
        changes[changesLine].push_back ({&x, x}),
        x = y;
}

int emptySets = 0;
void rollBack (int id)
{
    reverse (changes[id].begin (), changes[id].end ());
    for (auto it : changes[id])
        *it.first = it.second;
    changes[id].clear ();
    for (auto it : setChanges[id])
        emptySets -= S[it.first].empty (),
        S[it.first].insert (it.second);
    setChanges[id].clear ();
}

const int maxSize = 300009;
int aib[2][maxSize];

void update (int lin, int pos, int val)
{
    while (pos <= xCount)
        update (aib[lin][pos], val),
        pos += pos - (pos & (pos - 1));
}

int query (int lin, int pos)
{
    int ans = -INF;
    while (pos)
        ans = max (ans, aib[lin][pos]),
        pos &= pos - 1;
    return ans;
}

int firstBigger (int val)
{
    int p = 1, u = xCount, mij, ras = xCount + 1;
    while (p <= u)
    {
        mij = (p + u) >> 1;
        if (realX[mij] > val) ras = mij, u = mij - 1;
        else p = mij + 1;
    }
    return ras;
}

int lastSmaller (int val)
{
    int p = 1, u = xCount, mij, ras = 0;
    while (p <= u)
    {
        mij = (p + u) >> 1;
        if (realX[mij] < val) ras = mij, p = mij + 1;
        else u = mij - 1;
    }
    return ras;
}

int maxDist (int x)
{
    int v1 = query (0, xCount - x + 1) + realX[x];
    int v2 = query (1, x) - realX[x];
    return max (v1, v2);
}

void addSegm (int x0, int x2)
{
    int mid = (x0 + x2) / 2, pos = lastSmaller (mid + 1);
    if (pos >= 1) update (0, xCount - pos + 1, -x0);
    if (pos < xCount) update (1, pos + 1, x2);
}

void delPoint (int type, int x)
{
    auto it = S[type].lower_bound (x), it0 = it, it2 = it;
    int x0, x2;
    if (it0 == S[type].begin ()) x0 = -INF;
    else it0 --, x0 = *it0;
    it2 ++;
    if (it2 == S[type].end ()) x2 = +INF;
    else x2 = *it2;

    if (x0 != x && x2 != x)
        addSegm (x0, x2);

    setChanges[changesLine].push_back ({type, x});
    S[type].erase (it), emptySets += S[type].empty ();
}

void init ()
{
    for (int i=1; i<=N; i++)
        if (a[i] <= b[i])
            S[type[i]].insert (x[i]);
    for (int i=1; i<=xCount; i++)
        aib[0][i] = aib[1][i] = -INF;
    for (int i=1; i<=K; i++)
    {
        emptySets += S[i].empty ();
        int lastX = -INF;
        for (auto it : S[i])
            addSegm (lastX, it),
            lastX = it;
        addSegm (lastX, +INF);
    }
    changes[changesLine].clear ();
}

int mpX[300009];
vector < int > normT;
void normalize ()
{
    sort (normT.begin (), normT.end ());
    normT.erase (unique (normT.begin (), normT.end ()), normT.end ());
    timeCount = normT.size ();
    sort (mpX + 1, mpX + Q + 1);
    for (int i=1; i<=Q; i++)
        if (i == 1 || mpX[i] != mpX[i - 1])
            realX[++xCount] = mpX[i];
    for (int i=1; i<=Q; i++)
    {
        int p = 1, u = timeCount, mij, ras = 0;
        while (p <= u)
        {
            mij = (p + u) >> 1;
            if (normT[mij - 1] <= when[i]) ras = mij, p = mij + 1;
            else u = mij - 1;
        }
        when[i] = ras;
        location[i] = lastSmaller (location[i] + 1);
    }
    for (int i=1; i<=N; i++)
    {
        int p = 1, u = timeCount, mij, ras = timeCount + 1;
        while (p <= u)
        {
            mij = (p + u) >> 1;
            if (normT[mij - 1] >= a[i]) ras = mij, u = mij - 1;
            else p = mij + 1;
        }
        a[i] = ras, ras = 0, p = 1, u = timeCount;
        while (p <= u)
        {
            mij = (p + u) >> 1;
            if (normT[mij - 1] <= b[i]) ras = mij, p = mij + 1;
            else u = mij - 1;
        }
        b[i] = ras;
    }
}

vector < int > delList[1200009], qry[300009];
void addToDelList (int nod, int st, int dr, int x, int y, int val)
{
    if (x <= st && dr <= y)
    {
        delList[nod].push_back (val);
        return ;
    }
    int mij = (st + dr) >> 1, f1 = nod << 1, f2 = f1 | 1;
    if (x <= mij) addToDelList (f1, st, mij, x, y, val);
    if (mij < y) addToDelList (f2, mij + 1, dr, x, y, val);
}

void buildDelList ()
{
    for (int i=1; i<=N; i++)
    if (a[i] <= b[i])
    {
        if (a[i] > 1)
            addToDelList (1, 1, timeCount, 1, a[i] - 1, i);
        if (b[i] < timeCount)
            addToDelList (1, 1, timeCount, b[i] + 1, timeCount, i);
    }
}

void solveDC (int nod, int st, int dr)
{
    changesLine ++;
    for (auto it : delList[nod])
        delPoint (type[it], x[it]);
    if (st == dr)
    {
        for (auto it : qry[st])
            if (emptySets > 0) ans[it] = -1;
            else ans[it] = maxDist (location[it]);
    }
    else
    {
        int mij = (st + dr) >> 1, f1 = nod << 1, f2 = f1 | 1;
        solveDC (f1, st, mij);
        solveDC (f2, mij + 1, dr);
    }
    rollBack (changesLine), changesLine --;
}

void Read (int &x);
int main ()
{
//freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);

Read (N), Read (K), Read (Q), normT.resize (Q);
for (int i=1; i<=N; i++)
    Read (x[i]), Read (type[i]), Read (a[i]), Read (b[i]);
for (int i=1; i<=Q; i++)
    Read (location[i]), Read (when[i]),
    normT[i - 1] = when[i], mpX[i] = location[i];
normalize ();
init ();
buildDelList ();
for (int i=1; i<=Q; i++)
    qry[when[i]].push_back (i);
solveDC (1, 1, timeCount);
for (int i=1; i<=Q; i++)
    printf ("%d\n", ans[i]);
return 0;
}

const int maxl = 500000;
int pos = maxl - 1;
char buff[maxl];

void Next ()
{
    if (++pos == maxl)
        fread (buff, 1, maxl, stdin), pos = 0;
}

void Read (int &x)
{
    while (buff[pos] < '0' || buff[pos] > '9') Next ();
    for (x = 0; buff[pos] >= '0' && buff[pos] <= '9'; Next ()) x = x * 10 + buff[pos] - '0';
}

Compilation message

new_home.cpp: In function 'void Next()':
new_home.cpp:243:37: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         fread (buff, 1, maxl, stdin), pos = 0;
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	45 ms	49656 KB	Output is correct
2	Correct	50 ms	49764 KB	Output is correct
3	Correct	42 ms	49816 KB	Output is correct
4	Correct	44 ms	49864 KB	Output is correct
5	Correct	45 ms	49972 KB	Output is correct
6	Correct	56 ms	49972 KB	Output is correct
7	Correct	46 ms	49972 KB	Output is correct
8	Correct	53 ms	49972 KB	Output is correct
9	Correct	47 ms	49992 KB	Output is correct
10	Correct	50 ms	50312 KB	Output is correct
11	Correct	56 ms	50312 KB	Output is correct
12	Correct	48 ms	50312 KB	Output is correct
13	Correct	42 ms	50312 KB	Output is correct
14	Correct	56 ms	50312 KB	Output is correct
15	Correct	42 ms	50312 KB	Output is correct
16	Correct	45 ms	50312 KB	Output is correct
17	Correct	51 ms	50312 KB	Output is correct
18	Correct	50 ms	50312 KB	Output is correct
19	Correct	47 ms	50312 KB	Output is correct
20	Correct	46 ms	50312 KB	Output is correct
21	Correct	40 ms	50312 KB	Output is correct
22	Correct	41 ms	50312 KB	Output is correct
23	Correct	41 ms	50312 KB	Output is correct
24	Correct	40 ms	50312 KB	Output is correct
25	Correct	51 ms	50312 KB	Output is correct
26	Correct	47 ms	50312 KB	Output is correct
27	Correct	44 ms	50312 KB	Output is correct
28	Correct	50 ms	50312 KB	Output is correct
29	Correct	45 ms	50312 KB	Output is correct
30	Correct	46 ms	50312 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	45 ms	49656 KB	Output is correct
2	Correct	50 ms	49764 KB	Output is correct
3	Correct	42 ms	49816 KB	Output is correct
4	Correct	44 ms	49864 KB	Output is correct
5	Correct	45 ms	49972 KB	Output is correct
6	Correct	56 ms	49972 KB	Output is correct
7	Correct	46 ms	49972 KB	Output is correct
8	Correct	53 ms	49972 KB	Output is correct
9	Correct	47 ms	49992 KB	Output is correct
10	Correct	50 ms	50312 KB	Output is correct
11	Correct	56 ms	50312 KB	Output is correct
12	Correct	48 ms	50312 KB	Output is correct
13	Correct	42 ms	50312 KB	Output is correct
14	Correct	56 ms	50312 KB	Output is correct
15	Correct	42 ms	50312 KB	Output is correct
16	Correct	45 ms	50312 KB	Output is correct
17	Correct	51 ms	50312 KB	Output is correct
18	Correct	50 ms	50312 KB	Output is correct
19	Correct	47 ms	50312 KB	Output is correct
20	Correct	46 ms	50312 KB	Output is correct
21	Correct	40 ms	50312 KB	Output is correct
22	Correct	41 ms	50312 KB	Output is correct
23	Correct	41 ms	50312 KB	Output is correct
24	Correct	40 ms	50312 KB	Output is correct
25	Correct	51 ms	50312 KB	Output is correct
26	Correct	47 ms	50312 KB	Output is correct
27	Correct	44 ms	50312 KB	Output is correct
28	Correct	50 ms	50312 KB	Output is correct
29	Correct	45 ms	50312 KB	Output is correct
30	Correct	46 ms	50312 KB	Output is correct
31	Correct	1138 ms	70212 KB	Output is correct
32	Correct	235 ms	70212 KB	Output is correct
33	Correct	1181 ms	72324 KB	Output is correct
34	Correct	1031 ms	72332 KB	Output is correct
35	Correct	1089 ms	72332 KB	Output is correct
36	Correct	1313 ms	72332 KB	Output is correct
37	Correct	939 ms	72484 KB	Output is correct
38	Correct	868 ms	73528 KB	Output is correct
39	Correct	617 ms	73528 KB	Output is correct
40	Correct	748 ms	73528 KB	Output is correct
41	Correct	728 ms	73528 KB	Output is correct
42	Correct	739 ms	73528 KB	Output is correct
43	Correct	82 ms	73528 KB	Output is correct
44	Correct	787 ms	73528 KB	Output is correct
45	Correct	840 ms	73528 KB	Output is correct
46	Correct	918 ms	73528 KB	Output is correct
47	Correct	513 ms	73528 KB	Output is correct
48	Correct	496 ms	73528 KB	Output is correct
49	Correct	508 ms	73528 KB	Output is correct
50	Correct	476 ms	73528 KB	Output is correct
51	Correct	552 ms	73528 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	752 ms	101180 KB	Output is correct
2	Correct	820 ms	104456 KB	Output is correct
3	Correct	689 ms	104456 KB	Output is correct
4	Correct	865 ms	104456 KB	Output is correct
5	Correct	1077 ms	143460 KB	Output is correct
6	Correct	1028 ms	143460 KB	Output is correct
7	Correct	634 ms	143460 KB	Output is correct
8	Correct	804 ms	143460 KB	Output is correct
9	Correct	660 ms	143460 KB	Output is correct
10	Correct	648 ms	143460 KB	Output is correct
11	Correct	452 ms	143460 KB	Output is correct
12	Correct	515 ms	143460 KB	Output is correct

Subtask #4
0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4716 ms	146432 KB	Output is correct
2	Correct	884 ms	146432 KB	Output is correct
3	Execution timed out	5021 ms	147140 KB	Time limit exceeded
4	Halted	0 ms	0 KB	-

Subtask #5
35.0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	45 ms	49656 KB	Output is correct
2	Correct	50 ms	49764 KB	Output is correct
3	Correct	42 ms	49816 KB	Output is correct
4	Correct	44 ms	49864 KB	Output is correct
5	Correct	45 ms	49972 KB	Output is correct
6	Correct	56 ms	49972 KB	Output is correct
7	Correct	46 ms	49972 KB	Output is correct
8	Correct	53 ms	49972 KB	Output is correct
9	Correct	47 ms	49992 KB	Output is correct
10	Correct	50 ms	50312 KB	Output is correct
11	Correct	56 ms	50312 KB	Output is correct
12	Correct	48 ms	50312 KB	Output is correct
13	Correct	42 ms	50312 KB	Output is correct
14	Correct	56 ms	50312 KB	Output is correct
15	Correct	42 ms	50312 KB	Output is correct
16	Correct	45 ms	50312 KB	Output is correct
17	Correct	51 ms	50312 KB	Output is correct
18	Correct	50 ms	50312 KB	Output is correct
19	Correct	47 ms	50312 KB	Output is correct
20	Correct	46 ms	50312 KB	Output is correct
21	Correct	40 ms	50312 KB	Output is correct
22	Correct	41 ms	50312 KB	Output is correct
23	Correct	41 ms	50312 KB	Output is correct
24	Correct	40 ms	50312 KB	Output is correct
25	Correct	51 ms	50312 KB	Output is correct
26	Correct	47 ms	50312 KB	Output is correct
27	Correct	44 ms	50312 KB	Output is correct
28	Correct	50 ms	50312 KB	Output is correct
29	Correct	45 ms	50312 KB	Output is correct
30	Correct	46 ms	50312 KB	Output is correct
31	Correct	1138 ms	70212 KB	Output is correct
32	Correct	235 ms	70212 KB	Output is correct
33	Correct	1181 ms	72324 KB	Output is correct
34	Correct	1031 ms	72332 KB	Output is correct
35	Correct	1089 ms	72332 KB	Output is correct
36	Correct	1313 ms	72332 KB	Output is correct
37	Correct	939 ms	72484 KB	Output is correct
38	Correct	868 ms	73528 KB	Output is correct
39	Correct	617 ms	73528 KB	Output is correct
40	Correct	748 ms	73528 KB	Output is correct
41	Correct	728 ms	73528 KB	Output is correct
42	Correct	739 ms	73528 KB	Output is correct
43	Correct	82 ms	73528 KB	Output is correct
44	Correct	787 ms	73528 KB	Output is correct
45	Correct	840 ms	73528 KB	Output is correct
46	Correct	918 ms	73528 KB	Output is correct
47	Correct	513 ms	73528 KB	Output is correct
48	Correct	496 ms	73528 KB	Output is correct
49	Correct	508 ms	73528 KB	Output is correct
50	Correct	476 ms	73528 KB	Output is correct
51	Correct	552 ms	73528 KB	Output is correct
52	Correct	509 ms	147140 KB	Output is correct
53	Correct	585 ms	147140 KB	Output is correct
54	Correct	750 ms	147140 KB	Output is correct
55	Correct	570 ms	147140 KB	Output is correct
56	Correct	517 ms	147140 KB	Output is correct
57	Correct	682 ms	147140 KB	Output is correct
58	Correct	570 ms	147140 KB	Output is correct
59	Correct	520 ms	147140 KB	Output is correct
60	Correct	646 ms	147140 KB	Output is correct
61	Correct	66 ms	147140 KB	Output is correct
62	Correct	359 ms	147140 KB	Output is correct
63	Correct	477 ms	147140 KB	Output is correct
64	Correct	429 ms	147140 KB	Output is correct
65	Correct	743 ms	147140 KB	Output is correct
66	Correct	784 ms	147140 KB	Output is correct
67	Correct	230 ms	147140 KB	Output is correct

Subtask #6
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	45 ms	49656 KB	Output is correct
2	Correct	50 ms	49764 KB	Output is correct
3	Correct	42 ms	49816 KB	Output is correct
4	Correct	44 ms	49864 KB	Output is correct
5	Correct	45 ms	49972 KB	Output is correct
6	Correct	56 ms	49972 KB	Output is correct
7	Correct	46 ms	49972 KB	Output is correct
8	Correct	53 ms	49972 KB	Output is correct
9	Correct	47 ms	49992 KB	Output is correct
10	Correct	50 ms	50312 KB	Output is correct
11	Correct	56 ms	50312 KB	Output is correct
12	Correct	48 ms	50312 KB	Output is correct
13	Correct	42 ms	50312 KB	Output is correct
14	Correct	56 ms	50312 KB	Output is correct
15	Correct	42 ms	50312 KB	Output is correct
16	Correct	45 ms	50312 KB	Output is correct
17	Correct	51 ms	50312 KB	Output is correct
18	Correct	50 ms	50312 KB	Output is correct
19	Correct	47 ms	50312 KB	Output is correct
20	Correct	46 ms	50312 KB	Output is correct
21	Correct	40 ms	50312 KB	Output is correct
22	Correct	41 ms	50312 KB	Output is correct
23	Correct	41 ms	50312 KB	Output is correct
24	Correct	40 ms	50312 KB	Output is correct
25	Correct	51 ms	50312 KB	Output is correct
26	Correct	47 ms	50312 KB	Output is correct
27	Correct	44 ms	50312 KB	Output is correct
28	Correct	50 ms	50312 KB	Output is correct
29	Correct	45 ms	50312 KB	Output is correct
30	Correct	46 ms	50312 KB	Output is correct
31	Correct	1138 ms	70212 KB	Output is correct
32	Correct	235 ms	70212 KB	Output is correct
33	Correct	1181 ms	72324 KB	Output is correct
34	Correct	1031 ms	72332 KB	Output is correct
35	Correct	1089 ms	72332 KB	Output is correct
36	Correct	1313 ms	72332 KB	Output is correct
37	Correct	939 ms	72484 KB	Output is correct
38	Correct	868 ms	73528 KB	Output is correct
39	Correct	617 ms	73528 KB	Output is correct
40	Correct	748 ms	73528 KB	Output is correct
41	Correct	728 ms	73528 KB	Output is correct
42	Correct	739 ms	73528 KB	Output is correct
43	Correct	82 ms	73528 KB	Output is correct
44	Correct	787 ms	73528 KB	Output is correct
45	Correct	840 ms	73528 KB	Output is correct
46	Correct	918 ms	73528 KB	Output is correct
47	Correct	513 ms	73528 KB	Output is correct
48	Correct	496 ms	73528 KB	Output is correct
49	Correct	508 ms	73528 KB	Output is correct
50	Correct	476 ms	73528 KB	Output is correct
51	Correct	552 ms	73528 KB	Output is correct
52	Correct	752 ms	101180 KB	Output is correct
53	Correct	820 ms	104456 KB	Output is correct
54	Correct	689 ms	104456 KB	Output is correct
55	Correct	865 ms	104456 KB	Output is correct
56	Correct	1077 ms	143460 KB	Output is correct
57	Correct	1028 ms	143460 KB	Output is correct
58	Correct	634 ms	143460 KB	Output is correct
59	Correct	804 ms	143460 KB	Output is correct
60	Correct	660 ms	143460 KB	Output is correct
61	Correct	648 ms	143460 KB	Output is correct
62	Correct	452 ms	143460 KB	Output is correct
63	Correct	515 ms	143460 KB	Output is correct
64	Correct	4716 ms	146432 KB	Output is correct
65	Correct	884 ms	146432 KB	Output is correct
66	Execution timed out	5021 ms	147140 KB	Time limit exceeded
67	Halted	0 ms	0 KB	-

답안 #49705

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