답안 #49648 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
49648	2018-06-01T15:10:58 Z	SpaimaCarpatilor	새 집 (APIO18_new_home)	C++17	47 / 100	5000 ms	533832 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[600009];
const int INF = 5e8;
int changesLine = 0;
vector < pair < int*, int > > changes[20];
vector < multiset < int > > S;
vector < pair < int, int > > setChanges[20];

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 = 2400009;
int aint[2][maxSize];
void update (int lin, int nod, int st, int dr, int x, int y, int lazyVal)
{
    if (x <= st && dr <= y)
    {
        if (lin == 0) update (aint[lin][nod], lazyVal + realX[st] - realX[x]);
        else update (aint[lin][nod], lazyVal - (realX[st] - realX[x]));
        return ;
    }
    int mij = (st + dr) >> 1, f1 = nod << 1, f2 = f1 | 1;
    update (aint[lin][f1], aint[lin][nod]);
    if (lin == 0) update (aint[lin][f2], aint[lin][nod] + realX[mij + 1] - realX[st]);
    else update (aint[lin][f2], aint[lin][nod] - (realX[mij + 1] - realX[st]));
    if (x <= mij) update (lin, f1, st, mij, x, y, lazyVal);
    if (mij < y) update (lin, f2, mij + 1, dr, x, y, lazyVal);
}

int query (int lin, int nod, int st, int dr, int pos)
{
    if (st == dr) return aint[lin][nod];
    int mij = (st + dr) >> 1, ans = aint[lin][nod], curr;
    if (lin == 0) ans += realX[pos] - realX[st];
    else ans -= (realX[pos] - realX[st]);
    if (pos <= mij) curr = query (lin, nod << 1, st, mij, pos);
    else curr = query (lin, nod << 1 | 1, mij + 1, dr, pos);
    return max (ans, curr);
}

int maxDist (int x)
{
    int v1 = query (0, 1, 1, xCount, x), v2 = query (1, 1, 1, xCount, x);
    return max (v1, v2);
}

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

void addLine (int type, int bg, int nd)
{
    int x = firstBigger (bg - 1), y = lastSmaller (nd + 1);
    if (x <= y)
    {
        if (type == 0) update (0, 1, 1, xCount, x, y, realX[x] - bg);
        else update (1, 1, 1, xCount, x, y, nd - realX[x]);
    }
}

void addSegm (int x0, int x2)
{
    int mid = (x0 + x2) / 2;
    addLine (0, x0, mid);
    addLine (1, mid + 1, x2);
}

void delPoint (int type, int x)
{
    //printf ("del (%d, %d)\n", type, 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<=4 * xCount; i++)
        aint[0][i] = aint[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 ();
}

map < int, int > normT, mpX;
void normalize ()
{
    for (auto &it : normT)
        it.second = ++timeCount;
    for (auto &it : mpX)
        it.second = ++xCount, realX[xCount] = it.first;
    for (int i=1; i<=Q; i++)
        when[i] = normT[when[i]], location[i] = mpX[location[i]];
    for (int i=1; i<=N; i++)
        a[i] = normT[a[i]], b[i] = normT[b[i]], x[i] = mpX[x[i]];
}

vector < vector < int > > delList, qry;
void addToDelList (int nod, int st, int dr, int x, int y, int val)
{
    if (x <= st && dr <= y)
    {
        //printf ("add %d to delList[%d]\n", val, nod);
        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 ()
{
    delList.resize (4 * (timeCount + 1));
    for (int i=1; i<=N; 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], realX[x[it]]);
        //printf ("->size=%d\n", S[1].size ());
    }
    if (st == dr)
    {
        for (auto it : qry[st])
        {
            //printf ("solve %d (time=%d, location=%d)\n", it, when[it], location[it]);
            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);
    }
/*    for (auto it : delList[nod])
        printf ("add (%d, %d)\n", type[it], x[it]);*/
//    bool needToPrint = (setChanges[changesLine].size () > 0);
    rollBack (changesLine), changesLine --;
//    if (needToPrint) printf ("->size=%d\n", S[1].size ());
}

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

Read (N), Read (K), Read (Q), S.resize (K + 1);
for (int i=1; i<=N; i++)
    Read (x[i]), Read (type[i]), Read (a[i]), Read (b[i]),
    normT[a[i]] = 1, normT[b[i]] = 1, mpX[x[i]] = 1, S[type[i]].insert (x[i]);
for (int i=1; i<=Q; i++)
    Read (location[i]), Read (when[i]), normT[when[i]] = 1, mpX[location[i]] = 1;
normalize ();
init ();
/*for (int i=1; i<=Q; i++)
{
    int curr = maxDist (location[i]);
    if (curr > 2e8)
        curr = -1;
    printf ("%d\n", curr);
}
return 0;*/
buildDelList ();
qry.resize (timeCount + 1);
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:250: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	3 ms	376 KB	Output is correct
2	Correct	2 ms	488 KB	Output is correct
3	Correct	2 ms	488 KB	Output is correct
4	Correct	2 ms	488 KB	Output is correct
5	Correct	3 ms	688 KB	Output is correct
6	Correct	8 ms	1124 KB	Output is correct
7	Correct	4 ms	1176 KB	Output is correct
8	Correct	6 ms	1176 KB	Output is correct
9	Correct	4 ms	1176 KB	Output is correct
10	Correct	9 ms	1176 KB	Output is correct
11	Correct	6 ms	1232 KB	Output is correct
12	Correct	8 ms	1232 KB	Output is correct
13	Correct	7 ms	1232 KB	Output is correct
14	Correct	7 ms	1232 KB	Output is correct
15	Correct	6 ms	1272 KB	Output is correct
16	Correct	8 ms	1272 KB	Output is correct
17	Correct	8 ms	1276 KB	Output is correct
18	Correct	7 ms	1276 KB	Output is correct
19	Correct	7 ms	1276 KB	Output is correct
20	Correct	8 ms	1276 KB	Output is correct
21	Correct	3 ms	1276 KB	Output is correct
22	Correct	6 ms	1276 KB	Output is correct
23	Correct	5 ms	1276 KB	Output is correct
24	Correct	6 ms	1276 KB	Output is correct
25	Correct	7 ms	1276 KB	Output is correct
26	Correct	8 ms	1276 KB	Output is correct
27	Correct	5 ms	1276 KB	Output is correct
28	Correct	10 ms	1276 KB	Output is correct
29	Correct	7 ms	1276 KB	Output is correct
30	Correct	6 ms	1276 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	376 KB	Output is correct
2	Correct	2 ms	488 KB	Output is correct
3	Correct	2 ms	488 KB	Output is correct
4	Correct	2 ms	488 KB	Output is correct
5	Correct	3 ms	688 KB	Output is correct
6	Correct	8 ms	1124 KB	Output is correct
7	Correct	4 ms	1176 KB	Output is correct
8	Correct	6 ms	1176 KB	Output is correct
9	Correct	4 ms	1176 KB	Output is correct
10	Correct	9 ms	1176 KB	Output is correct
11	Correct	6 ms	1232 KB	Output is correct
12	Correct	8 ms	1232 KB	Output is correct
13	Correct	7 ms	1232 KB	Output is correct
14	Correct	7 ms	1232 KB	Output is correct
15	Correct	6 ms	1272 KB	Output is correct
16	Correct	8 ms	1272 KB	Output is correct
17	Correct	8 ms	1276 KB	Output is correct
18	Correct	7 ms	1276 KB	Output is correct
19	Correct	7 ms	1276 KB	Output is correct
20	Correct	8 ms	1276 KB	Output is correct
21	Correct	3 ms	1276 KB	Output is correct
22	Correct	6 ms	1276 KB	Output is correct
23	Correct	5 ms	1276 KB	Output is correct
24	Correct	6 ms	1276 KB	Output is correct
25	Correct	7 ms	1276 KB	Output is correct
26	Correct	8 ms	1276 KB	Output is correct
27	Correct	5 ms	1276 KB	Output is correct
28	Correct	10 ms	1276 KB	Output is correct
29	Correct	7 ms	1276 KB	Output is correct
30	Correct	6 ms	1276 KB	Output is correct
31	Correct	3875 ms	92136 KB	Output is correct
32	Correct	176 ms	92136 KB	Output is correct
33	Correct	3712 ms	92136 KB	Output is correct
34	Correct	4053 ms	94648 KB	Output is correct
35	Correct	3935 ms	94648 KB	Output is correct
36	Correct	3514 ms	94648 KB	Output is correct
37	Correct	2993 ms	94648 KB	Output is correct
38	Correct	2778 ms	94648 KB	Output is correct
39	Correct	2175 ms	94648 KB	Output is correct
40	Correct	2410 ms	94648 KB	Output is correct
41	Correct	2796 ms	94648 KB	Output is correct
42	Correct	3289 ms	94648 KB	Output is correct
43	Correct	45 ms	94648 KB	Output is correct
44	Correct	3505 ms	94648 KB	Output is correct
45	Correct	3510 ms	94648 KB	Output is correct
46	Correct	3511 ms	94648 KB	Output is correct
47	Correct	1636 ms	94648 KB	Output is correct
48	Correct	1497 ms	94648 KB	Output is correct
49	Correct	1725 ms	94648 KB	Output is correct
50	Correct	1698 ms	94648 KB	Output is correct
51	Correct	2072 ms	94648 KB	Output is correct

Subtask #3
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	4099 ms	397172 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
2	Halted	0 ms	0 KB	-

Subtask #4
0 / 23.0

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

Subtask #5
35.0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	376 KB	Output is correct
2	Correct	2 ms	488 KB	Output is correct
3	Correct	2 ms	488 KB	Output is correct
4	Correct	2 ms	488 KB	Output is correct
5	Correct	3 ms	688 KB	Output is correct
6	Correct	8 ms	1124 KB	Output is correct
7	Correct	4 ms	1176 KB	Output is correct
8	Correct	6 ms	1176 KB	Output is correct
9	Correct	4 ms	1176 KB	Output is correct
10	Correct	9 ms	1176 KB	Output is correct
11	Correct	6 ms	1232 KB	Output is correct
12	Correct	8 ms	1232 KB	Output is correct
13	Correct	7 ms	1232 KB	Output is correct
14	Correct	7 ms	1232 KB	Output is correct
15	Correct	6 ms	1272 KB	Output is correct
16	Correct	8 ms	1272 KB	Output is correct
17	Correct	8 ms	1276 KB	Output is correct
18	Correct	7 ms	1276 KB	Output is correct
19	Correct	7 ms	1276 KB	Output is correct
20	Correct	8 ms	1276 KB	Output is correct
21	Correct	3 ms	1276 KB	Output is correct
22	Correct	6 ms	1276 KB	Output is correct
23	Correct	5 ms	1276 KB	Output is correct
24	Correct	6 ms	1276 KB	Output is correct
25	Correct	7 ms	1276 KB	Output is correct
26	Correct	8 ms	1276 KB	Output is correct
27	Correct	5 ms	1276 KB	Output is correct
28	Correct	10 ms	1276 KB	Output is correct
29	Correct	7 ms	1276 KB	Output is correct
30	Correct	6 ms	1276 KB	Output is correct
31	Correct	3875 ms	92136 KB	Output is correct
32	Correct	176 ms	92136 KB	Output is correct
33	Correct	3712 ms	92136 KB	Output is correct
34	Correct	4053 ms	94648 KB	Output is correct
35	Correct	3935 ms	94648 KB	Output is correct
36	Correct	3514 ms	94648 KB	Output is correct
37	Correct	2993 ms	94648 KB	Output is correct
38	Correct	2778 ms	94648 KB	Output is correct
39	Correct	2175 ms	94648 KB	Output is correct
40	Correct	2410 ms	94648 KB	Output is correct
41	Correct	2796 ms	94648 KB	Output is correct
42	Correct	3289 ms	94648 KB	Output is correct
43	Correct	45 ms	94648 KB	Output is correct
44	Correct	3505 ms	94648 KB	Output is correct
45	Correct	3510 ms	94648 KB	Output is correct
46	Correct	3511 ms	94648 KB	Output is correct
47	Correct	1636 ms	94648 KB	Output is correct
48	Correct	1497 ms	94648 KB	Output is correct
49	Correct	1725 ms	94648 KB	Output is correct
50	Correct	1698 ms	94648 KB	Output is correct
51	Correct	2072 ms	94648 KB	Output is correct
52	Correct	1574 ms	533832 KB	Output is correct
53	Correct	1538 ms	533832 KB	Output is correct
54	Correct	2688 ms	533832 KB	Output is correct
55	Correct	2716 ms	533832 KB	Output is correct
56	Correct	2195 ms	533832 KB	Output is correct
57	Correct	3089 ms	533832 KB	Output is correct
58	Correct	2486 ms	533832 KB	Output is correct
59	Correct	2345 ms	533832 KB	Output is correct
60	Correct	3045 ms	533832 KB	Output is correct
61	Correct	41 ms	533832 KB	Output is correct
62	Correct	1390 ms	533832 KB	Output is correct
63	Correct	2027 ms	533832 KB	Output is correct
64	Correct	1873 ms	533832 KB	Output is correct
65	Correct	2410 ms	533832 KB	Output is correct
66	Correct	2845 ms	533832 KB	Output is correct
67	Correct	308 ms	533832 KB	Output is correct

Subtask #6
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	376 KB	Output is correct
2	Correct	2 ms	488 KB	Output is correct
3	Correct	2 ms	488 KB	Output is correct
4	Correct	2 ms	488 KB	Output is correct
5	Correct	3 ms	688 KB	Output is correct
6	Correct	8 ms	1124 KB	Output is correct
7	Correct	4 ms	1176 KB	Output is correct
8	Correct	6 ms	1176 KB	Output is correct
9	Correct	4 ms	1176 KB	Output is correct
10	Correct	9 ms	1176 KB	Output is correct
11	Correct	6 ms	1232 KB	Output is correct
12	Correct	8 ms	1232 KB	Output is correct
13	Correct	7 ms	1232 KB	Output is correct
14	Correct	7 ms	1232 KB	Output is correct
15	Correct	6 ms	1272 KB	Output is correct
16	Correct	8 ms	1272 KB	Output is correct
17	Correct	8 ms	1276 KB	Output is correct
18	Correct	7 ms	1276 KB	Output is correct
19	Correct	7 ms	1276 KB	Output is correct
20	Correct	8 ms	1276 KB	Output is correct
21	Correct	3 ms	1276 KB	Output is correct
22	Correct	6 ms	1276 KB	Output is correct
23	Correct	5 ms	1276 KB	Output is correct
24	Correct	6 ms	1276 KB	Output is correct
25	Correct	7 ms	1276 KB	Output is correct
26	Correct	8 ms	1276 KB	Output is correct
27	Correct	5 ms	1276 KB	Output is correct
28	Correct	10 ms	1276 KB	Output is correct
29	Correct	7 ms	1276 KB	Output is correct
30	Correct	6 ms	1276 KB	Output is correct
31	Correct	3875 ms	92136 KB	Output is correct
32	Correct	176 ms	92136 KB	Output is correct
33	Correct	3712 ms	92136 KB	Output is correct
34	Correct	4053 ms	94648 KB	Output is correct
35	Correct	3935 ms	94648 KB	Output is correct
36	Correct	3514 ms	94648 KB	Output is correct
37	Correct	2993 ms	94648 KB	Output is correct
38	Correct	2778 ms	94648 KB	Output is correct
39	Correct	2175 ms	94648 KB	Output is correct
40	Correct	2410 ms	94648 KB	Output is correct
41	Correct	2796 ms	94648 KB	Output is correct
42	Correct	3289 ms	94648 KB	Output is correct
43	Correct	45 ms	94648 KB	Output is correct
44	Correct	3505 ms	94648 KB	Output is correct
45	Correct	3510 ms	94648 KB	Output is correct
46	Correct	3511 ms	94648 KB	Output is correct
47	Correct	1636 ms	94648 KB	Output is correct
48	Correct	1497 ms	94648 KB	Output is correct
49	Correct	1725 ms	94648 KB	Output is correct
50	Correct	1698 ms	94648 KB	Output is correct
51	Correct	2072 ms	94648 KB	Output is correct
52	Runtime error	4099 ms	397172 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
53	Halted	0 ms	0 KB	-

답안 #49648

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 7.0 / 7.0

Subtask #3 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
0 / 10.0

Subtask #4
0 / 23.0

Subtask #5
35.0 / 35.0

Subtask #6
0 / 20.0