답안 #49719 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
49719	2018-06-02T10:01:01 Z	SpaimaCarpatilor	새 집 (APIO18_new_home)	C++17	57 / 100	5000 ms	129624 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 < pair < int, int > > S;
int setSize[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 -= (setSize[it.first] == 0),
        S.insert (it), setSize[it.first] ++;
    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 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;
    if (mid < realX[1]) pos = 0;
    else pos = lower_bound (realX + 1, realX + xCount + 1, mid + 1) - realX - 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.lower_bound ({type, x}), it0 = it, it2 = it;
    int x0 = -INF, x2 = +INF;
    if (it0 != S.begin ())
    {
        it0 --;
        if (it0->first == type) x0 = it0->second;;
    }
    it2 ++;
    if (it2 != S.end () && it2->first == type)
        x2 = it2->second;

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

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

void init ()
{
    for (int i=1; i<=N; i++)
        if (a[i] <= b[i])
            S.insert ({type[i], x[i]}), setSize[type[i]] ++;
    for (int i=1; i<=xCount; i++)
        aib[0][i] = aib[1][i] = -INF;
    auto it = S.begin ();
    for (int i=1; i<=K; i++)
    {
        emptySets += (setSize[i] == 0);
        int lastX = -INF;
        while (it != S.end () && it->first == i)
            addSegm (lastX, it->second),
            lastX = it->second, 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++)
        when[i] = lower_bound (normT.begin (), normT.end (), when[i]) - normT.begin () + 1,
        location[i] = lower_bound (realX + 1, realX + xCount, location[i]) - realX;
    for (int i=1; i<=N; i++)
    {
        a[i] = lower_bound (normT.begin (), normT.end (), a[i]) - normT.begin () + 1;
        if (b[i] < normT[0]) b[i] = 0;
        else b[i] = lower_bound (normT.begin (), normT.end (), b[i] + 1) - normT.begin ();
    }
}

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 ("100", "r", stdin);
//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:206: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	30 ms	35576 KB	Output is correct
2	Correct	29 ms	35688 KB	Output is correct
3	Correct	32 ms	35756 KB	Output is correct
4	Correct	33 ms	35784 KB	Output is correct
5	Correct	35 ms	35808 KB	Output is correct
6	Correct	35 ms	36052 KB	Output is correct
7	Correct	35 ms	36052 KB	Output is correct
8	Correct	38 ms	36052 KB	Output is correct
9	Correct	34 ms	36052 KB	Output is correct
10	Correct	34 ms	36052 KB	Output is correct
11	Correct	37 ms	36052 KB	Output is correct
12	Correct	38 ms	36052 KB	Output is correct
13	Correct	33 ms	36052 KB	Output is correct
14	Correct	32 ms	36052 KB	Output is correct
15	Correct	32 ms	36052 KB	Output is correct
16	Correct	32 ms	36052 KB	Output is correct
17	Correct	35 ms	36052 KB	Output is correct
18	Correct	34 ms	36052 KB	Output is correct
19	Correct	31 ms	36052 KB	Output is correct
20	Correct	32 ms	36052 KB	Output is correct
21	Correct	32 ms	36052 KB	Output is correct
22	Correct	31 ms	36052 KB	Output is correct
23	Correct	31 ms	36052 KB	Output is correct
24	Correct	38 ms	36052 KB	Output is correct
25	Correct	33 ms	36052 KB	Output is correct
26	Correct	34 ms	36068 KB	Output is correct
27	Correct	32 ms	36068 KB	Output is correct
28	Correct	37 ms	36068 KB	Output is correct
29	Correct	36 ms	36068 KB	Output is correct
30	Correct	32 ms	36068 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	30 ms	35576 KB	Output is correct
2	Correct	29 ms	35688 KB	Output is correct
3	Correct	32 ms	35756 KB	Output is correct
4	Correct	33 ms	35784 KB	Output is correct
5	Correct	35 ms	35808 KB	Output is correct
6	Correct	35 ms	36052 KB	Output is correct
7	Correct	35 ms	36052 KB	Output is correct
8	Correct	38 ms	36052 KB	Output is correct
9	Correct	34 ms	36052 KB	Output is correct
10	Correct	34 ms	36052 KB	Output is correct
11	Correct	37 ms	36052 KB	Output is correct
12	Correct	38 ms	36052 KB	Output is correct
13	Correct	33 ms	36052 KB	Output is correct
14	Correct	32 ms	36052 KB	Output is correct
15	Correct	32 ms	36052 KB	Output is correct
16	Correct	32 ms	36052 KB	Output is correct
17	Correct	35 ms	36052 KB	Output is correct
18	Correct	34 ms	36052 KB	Output is correct
19	Correct	31 ms	36052 KB	Output is correct
20	Correct	32 ms	36052 KB	Output is correct
21	Correct	32 ms	36052 KB	Output is correct
22	Correct	31 ms	36052 KB	Output is correct
23	Correct	31 ms	36052 KB	Output is correct
24	Correct	38 ms	36052 KB	Output is correct
25	Correct	33 ms	36052 KB	Output is correct
26	Correct	34 ms	36068 KB	Output is correct
27	Correct	32 ms	36068 KB	Output is correct
28	Correct	37 ms	36068 KB	Output is correct
29	Correct	36 ms	36068 KB	Output is correct
30	Correct	32 ms	36068 KB	Output is correct
31	Correct	1439 ms	55852 KB	Output is correct
32	Correct	230 ms	55852 KB	Output is correct
33	Correct	1287 ms	58204 KB	Output is correct
34	Correct	1614 ms	58204 KB	Output is correct
35	Correct	1239 ms	58204 KB	Output is correct
36	Correct	1214 ms	58204 KB	Output is correct
37	Correct	900 ms	58484 KB	Output is correct
38	Correct	877 ms	59416 KB	Output is correct
39	Correct	645 ms	59416 KB	Output is correct
40	Correct	735 ms	59416 KB	Output is correct
41	Correct	811 ms	59416 KB	Output is correct
42	Correct	872 ms	59416 KB	Output is correct
43	Correct	63 ms	59416 KB	Output is correct
44	Correct	970 ms	59416 KB	Output is correct
45	Correct	898 ms	59416 KB	Output is correct
46	Correct	868 ms	59416 KB	Output is correct
47	Correct	520 ms	59416 KB	Output is correct
48	Correct	529 ms	59416 KB	Output is correct
49	Correct	572 ms	59416 KB	Output is correct
50	Correct	572 ms	59416 KB	Output is correct
51	Correct	574 ms	59416 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1039 ms	87460 KB	Output is correct
2	Correct	1099 ms	90356 KB	Output is correct
3	Correct	1014 ms	90356 KB	Output is correct
4	Correct	995 ms	90356 KB	Output is correct
5	Correct	1064 ms	129372 KB	Output is correct
6	Correct	1016 ms	129372 KB	Output is correct
7	Correct	611 ms	129372 KB	Output is correct
8	Correct	701 ms	129372 KB	Output is correct
9	Correct	720 ms	129372 KB	Output is correct
10	Correct	777 ms	129372 KB	Output is correct
11	Correct	472 ms	129372 KB	Output is correct
12	Correct	545 ms	129372 KB	Output is correct

Subtask #4
0 / 23.0

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

Subtask #5
35.0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	30 ms	35576 KB	Output is correct
2	Correct	29 ms	35688 KB	Output is correct
3	Correct	32 ms	35756 KB	Output is correct
4	Correct	33 ms	35784 KB	Output is correct
5	Correct	35 ms	35808 KB	Output is correct
6	Correct	35 ms	36052 KB	Output is correct
7	Correct	35 ms	36052 KB	Output is correct
8	Correct	38 ms	36052 KB	Output is correct
9	Correct	34 ms	36052 KB	Output is correct
10	Correct	34 ms	36052 KB	Output is correct
11	Correct	37 ms	36052 KB	Output is correct
12	Correct	38 ms	36052 KB	Output is correct
13	Correct	33 ms	36052 KB	Output is correct
14	Correct	32 ms	36052 KB	Output is correct
15	Correct	32 ms	36052 KB	Output is correct
16	Correct	32 ms	36052 KB	Output is correct
17	Correct	35 ms	36052 KB	Output is correct
18	Correct	34 ms	36052 KB	Output is correct
19	Correct	31 ms	36052 KB	Output is correct
20	Correct	32 ms	36052 KB	Output is correct
21	Correct	32 ms	36052 KB	Output is correct
22	Correct	31 ms	36052 KB	Output is correct
23	Correct	31 ms	36052 KB	Output is correct
24	Correct	38 ms	36052 KB	Output is correct
25	Correct	33 ms	36052 KB	Output is correct
26	Correct	34 ms	36068 KB	Output is correct
27	Correct	32 ms	36068 KB	Output is correct
28	Correct	37 ms	36068 KB	Output is correct
29	Correct	36 ms	36068 KB	Output is correct
30	Correct	32 ms	36068 KB	Output is correct
31	Correct	1439 ms	55852 KB	Output is correct
32	Correct	230 ms	55852 KB	Output is correct
33	Correct	1287 ms	58204 KB	Output is correct
34	Correct	1614 ms	58204 KB	Output is correct
35	Correct	1239 ms	58204 KB	Output is correct
36	Correct	1214 ms	58204 KB	Output is correct
37	Correct	900 ms	58484 KB	Output is correct
38	Correct	877 ms	59416 KB	Output is correct
39	Correct	645 ms	59416 KB	Output is correct
40	Correct	735 ms	59416 KB	Output is correct
41	Correct	811 ms	59416 KB	Output is correct
42	Correct	872 ms	59416 KB	Output is correct
43	Correct	63 ms	59416 KB	Output is correct
44	Correct	970 ms	59416 KB	Output is correct
45	Correct	898 ms	59416 KB	Output is correct
46	Correct	868 ms	59416 KB	Output is correct
47	Correct	520 ms	59416 KB	Output is correct
48	Correct	529 ms	59416 KB	Output is correct
49	Correct	572 ms	59416 KB	Output is correct
50	Correct	572 ms	59416 KB	Output is correct
51	Correct	574 ms	59416 KB	Output is correct
52	Correct	1055 ms	129624 KB	Output is correct
53	Correct	846 ms	129624 KB	Output is correct
54	Correct	1114 ms	129624 KB	Output is correct
55	Correct	808 ms	129624 KB	Output is correct
56	Correct	565 ms	129624 KB	Output is correct
57	Correct	892 ms	129624 KB	Output is correct
58	Correct	941 ms	129624 KB	Output is correct
59	Correct	860 ms	129624 KB	Output is correct
60	Correct	1004 ms	129624 KB	Output is correct
61	Correct	78 ms	129624 KB	Output is correct
62	Correct	807 ms	129624 KB	Output is correct
63	Correct	872 ms	129624 KB	Output is correct
64	Correct	979 ms	129624 KB	Output is correct
65	Correct	964 ms	129624 KB	Output is correct
66	Correct	741 ms	129624 KB	Output is correct
67	Correct	228 ms	129624 KB	Output is correct

Subtask #6
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	30 ms	35576 KB	Output is correct
2	Correct	29 ms	35688 KB	Output is correct
3	Correct	32 ms	35756 KB	Output is correct
4	Correct	33 ms	35784 KB	Output is correct
5	Correct	35 ms	35808 KB	Output is correct
6	Correct	35 ms	36052 KB	Output is correct
7	Correct	35 ms	36052 KB	Output is correct
8	Correct	38 ms	36052 KB	Output is correct
9	Correct	34 ms	36052 KB	Output is correct
10	Correct	34 ms	36052 KB	Output is correct
11	Correct	37 ms	36052 KB	Output is correct
12	Correct	38 ms	36052 KB	Output is correct
13	Correct	33 ms	36052 KB	Output is correct
14	Correct	32 ms	36052 KB	Output is correct
15	Correct	32 ms	36052 KB	Output is correct
16	Correct	32 ms	36052 KB	Output is correct
17	Correct	35 ms	36052 KB	Output is correct
18	Correct	34 ms	36052 KB	Output is correct
19	Correct	31 ms	36052 KB	Output is correct
20	Correct	32 ms	36052 KB	Output is correct
21	Correct	32 ms	36052 KB	Output is correct
22	Correct	31 ms	36052 KB	Output is correct
23	Correct	31 ms	36052 KB	Output is correct
24	Correct	38 ms	36052 KB	Output is correct
25	Correct	33 ms	36052 KB	Output is correct
26	Correct	34 ms	36068 KB	Output is correct
27	Correct	32 ms	36068 KB	Output is correct
28	Correct	37 ms	36068 KB	Output is correct
29	Correct	36 ms	36068 KB	Output is correct
30	Correct	32 ms	36068 KB	Output is correct
31	Correct	1439 ms	55852 KB	Output is correct
32	Correct	230 ms	55852 KB	Output is correct
33	Correct	1287 ms	58204 KB	Output is correct
34	Correct	1614 ms	58204 KB	Output is correct
35	Correct	1239 ms	58204 KB	Output is correct
36	Correct	1214 ms	58204 KB	Output is correct
37	Correct	900 ms	58484 KB	Output is correct
38	Correct	877 ms	59416 KB	Output is correct
39	Correct	645 ms	59416 KB	Output is correct
40	Correct	735 ms	59416 KB	Output is correct
41	Correct	811 ms	59416 KB	Output is correct
42	Correct	872 ms	59416 KB	Output is correct
43	Correct	63 ms	59416 KB	Output is correct
44	Correct	970 ms	59416 KB	Output is correct
45	Correct	898 ms	59416 KB	Output is correct
46	Correct	868 ms	59416 KB	Output is correct
47	Correct	520 ms	59416 KB	Output is correct
48	Correct	529 ms	59416 KB	Output is correct
49	Correct	572 ms	59416 KB	Output is correct
50	Correct	572 ms	59416 KB	Output is correct
51	Correct	574 ms	59416 KB	Output is correct
52	Correct	1039 ms	87460 KB	Output is correct
53	Correct	1099 ms	90356 KB	Output is correct
54	Correct	1014 ms	90356 KB	Output is correct
55	Correct	995 ms	90356 KB	Output is correct
56	Correct	1064 ms	129372 KB	Output is correct
57	Correct	1016 ms	129372 KB	Output is correct
58	Correct	611 ms	129372 KB	Output is correct
59	Correct	701 ms	129372 KB	Output is correct
60	Correct	720 ms	129372 KB	Output is correct
61	Correct	777 ms	129372 KB	Output is correct
62	Correct	472 ms	129372 KB	Output is correct
63	Correct	545 ms	129372 KB	Output is correct
64	Execution timed out	5031 ms	129624 KB	Time limit exceeded
65	Halted	0 ms	0 KB	-

답안 #49719

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