답안 #49703 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
49703	2018-06-02T09:03:21 Z	SpaimaCarpatilor	새 집 (APIO18_new_home)	C++17	57 / 100	5000 ms	132368 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];
vector < multiset < int > > S;
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 < vector < int > > delList, qry;
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 ()
{
    delList.resize (4 * (timeCount + 1));
    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), S.resize (K + 1), 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 ();
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:245: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	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	520 KB	Output is correct
4	Correct	2 ms	596 KB	Output is correct
5	Correct	3 ms	596 KB	Output is correct
6	Correct	5 ms	676 KB	Output is correct
7	Correct	4 ms	800 KB	Output is correct
8	Correct	4 ms	800 KB	Output is correct
9	Correct	4 ms	800 KB	Output is correct
10	Correct	4 ms	848 KB	Output is correct
11	Correct	4 ms	848 KB	Output is correct
12	Correct	5 ms	868 KB	Output is correct
13	Correct	4 ms	868 KB	Output is correct
14	Correct	4 ms	868 KB	Output is correct
15	Correct	4 ms	868 KB	Output is correct
16	Correct	3 ms	868 KB	Output is correct
17	Correct	5 ms	868 KB	Output is correct
18	Correct	4 ms	868 KB	Output is correct
19	Correct	4 ms	868 KB	Output is correct
20	Correct	4 ms	868 KB	Output is correct
21	Correct	3 ms	868 KB	Output is correct
22	Correct	3 ms	868 KB	Output is correct
23	Correct	3 ms	868 KB	Output is correct
24	Correct	4 ms	868 KB	Output is correct
25	Correct	4 ms	868 KB	Output is correct
26	Correct	4 ms	868 KB	Output is correct
27	Correct	3 ms	868 KB	Output is correct
28	Correct	4 ms	868 KB	Output is correct
29	Correct	4 ms	868 KB	Output is correct
30	Correct	4 ms	868 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	520 KB	Output is correct
4	Correct	2 ms	596 KB	Output is correct
5	Correct	3 ms	596 KB	Output is correct
6	Correct	5 ms	676 KB	Output is correct
7	Correct	4 ms	800 KB	Output is correct
8	Correct	4 ms	800 KB	Output is correct
9	Correct	4 ms	800 KB	Output is correct
10	Correct	4 ms	848 KB	Output is correct
11	Correct	4 ms	848 KB	Output is correct
12	Correct	5 ms	868 KB	Output is correct
13	Correct	4 ms	868 KB	Output is correct
14	Correct	4 ms	868 KB	Output is correct
15	Correct	4 ms	868 KB	Output is correct
16	Correct	3 ms	868 KB	Output is correct
17	Correct	5 ms	868 KB	Output is correct
18	Correct	4 ms	868 KB	Output is correct
19	Correct	4 ms	868 KB	Output is correct
20	Correct	4 ms	868 KB	Output is correct
21	Correct	3 ms	868 KB	Output is correct
22	Correct	3 ms	868 KB	Output is correct
23	Correct	3 ms	868 KB	Output is correct
24	Correct	4 ms	868 KB	Output is correct
25	Correct	4 ms	868 KB	Output is correct
26	Correct	4 ms	868 KB	Output is correct
27	Correct	3 ms	868 KB	Output is correct
28	Correct	4 ms	868 KB	Output is correct
29	Correct	4 ms	868 KB	Output is correct
30	Correct	4 ms	868 KB	Output is correct
31	Correct	1162 ms	27932 KB	Output is correct
32	Correct	223 ms	27932 KB	Output is correct
33	Correct	1350 ms	29908 KB	Output is correct
34	Correct	1131 ms	30100 KB	Output is correct
35	Correct	1214 ms	30100 KB	Output is correct
36	Correct	1097 ms	30100 KB	Output is correct
37	Correct	904 ms	30260 KB	Output is correct
38	Correct	855 ms	31236 KB	Output is correct
39	Correct	607 ms	31236 KB	Output is correct
40	Correct	635 ms	31236 KB	Output is correct
41	Correct	651 ms	31236 KB	Output is correct
42	Correct	700 ms	31236 KB	Output is correct
43	Correct	47 ms	31236 KB	Output is correct
44	Correct	745 ms	31236 KB	Output is correct
45	Correct	735 ms	31236 KB	Output is correct
46	Correct	746 ms	31236 KB	Output is correct
47	Correct	430 ms	31236 KB	Output is correct
48	Correct	447 ms	31236 KB	Output is correct
49	Correct	536 ms	31236 KB	Output is correct
50	Correct	423 ms	31236 KB	Output is correct
51	Correct	506 ms	31236 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1037 ms	89936 KB	Output is correct
2	Correct	1002 ms	90228 KB	Output is correct
3	Correct	720 ms	90680 KB	Output is correct
4	Correct	785 ms	90680 KB	Output is correct
5	Correct	865 ms	124304 KB	Output is correct
6	Correct	794 ms	124304 KB	Output is correct
7	Correct	548 ms	124304 KB	Output is correct
8	Correct	656 ms	124304 KB	Output is correct
9	Correct	797 ms	124304 KB	Output is correct
10	Correct	986 ms	124304 KB	Output is correct
11	Correct	494 ms	124304 KB	Output is correct
12	Correct	492 ms	124304 KB	Output is correct

Subtask #4
0 / 23.0

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

Subtask #5
35.0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	520 KB	Output is correct
4	Correct	2 ms	596 KB	Output is correct
5	Correct	3 ms	596 KB	Output is correct
6	Correct	5 ms	676 KB	Output is correct
7	Correct	4 ms	800 KB	Output is correct
8	Correct	4 ms	800 KB	Output is correct
9	Correct	4 ms	800 KB	Output is correct
10	Correct	4 ms	848 KB	Output is correct
11	Correct	4 ms	848 KB	Output is correct
12	Correct	5 ms	868 KB	Output is correct
13	Correct	4 ms	868 KB	Output is correct
14	Correct	4 ms	868 KB	Output is correct
15	Correct	4 ms	868 KB	Output is correct
16	Correct	3 ms	868 KB	Output is correct
17	Correct	5 ms	868 KB	Output is correct
18	Correct	4 ms	868 KB	Output is correct
19	Correct	4 ms	868 KB	Output is correct
20	Correct	4 ms	868 KB	Output is correct
21	Correct	3 ms	868 KB	Output is correct
22	Correct	3 ms	868 KB	Output is correct
23	Correct	3 ms	868 KB	Output is correct
24	Correct	4 ms	868 KB	Output is correct
25	Correct	4 ms	868 KB	Output is correct
26	Correct	4 ms	868 KB	Output is correct
27	Correct	3 ms	868 KB	Output is correct
28	Correct	4 ms	868 KB	Output is correct
29	Correct	4 ms	868 KB	Output is correct
30	Correct	4 ms	868 KB	Output is correct
31	Correct	1162 ms	27932 KB	Output is correct
32	Correct	223 ms	27932 KB	Output is correct
33	Correct	1350 ms	29908 KB	Output is correct
34	Correct	1131 ms	30100 KB	Output is correct
35	Correct	1214 ms	30100 KB	Output is correct
36	Correct	1097 ms	30100 KB	Output is correct
37	Correct	904 ms	30260 KB	Output is correct
38	Correct	855 ms	31236 KB	Output is correct
39	Correct	607 ms	31236 KB	Output is correct
40	Correct	635 ms	31236 KB	Output is correct
41	Correct	651 ms	31236 KB	Output is correct
42	Correct	700 ms	31236 KB	Output is correct
43	Correct	47 ms	31236 KB	Output is correct
44	Correct	745 ms	31236 KB	Output is correct
45	Correct	735 ms	31236 KB	Output is correct
46	Correct	746 ms	31236 KB	Output is correct
47	Correct	430 ms	31236 KB	Output is correct
48	Correct	447 ms	31236 KB	Output is correct
49	Correct	536 ms	31236 KB	Output is correct
50	Correct	423 ms	31236 KB	Output is correct
51	Correct	506 ms	31236 KB	Output is correct
52	Correct	463 ms	132368 KB	Output is correct
53	Correct	425 ms	132368 KB	Output is correct
54	Correct	478 ms	132368 KB	Output is correct
55	Correct	492 ms	132368 KB	Output is correct
56	Correct	442 ms	132368 KB	Output is correct
57	Correct	577 ms	132368 KB	Output is correct
58	Correct	489 ms	132368 KB	Output is correct
59	Correct	470 ms	132368 KB	Output is correct
60	Correct	539 ms	132368 KB	Output is correct
61	Correct	28 ms	132368 KB	Output is correct
62	Correct	301 ms	132368 KB	Output is correct
63	Correct	501 ms	132368 KB	Output is correct
64	Correct	465 ms	132368 KB	Output is correct
65	Correct	460 ms	132368 KB	Output is correct
66	Correct	541 ms	132368 KB	Output is correct
67	Correct	127 ms	132368 KB	Output is correct

Subtask #6
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	520 KB	Output is correct
4	Correct	2 ms	596 KB	Output is correct
5	Correct	3 ms	596 KB	Output is correct
6	Correct	5 ms	676 KB	Output is correct
7	Correct	4 ms	800 KB	Output is correct
8	Correct	4 ms	800 KB	Output is correct
9	Correct	4 ms	800 KB	Output is correct
10	Correct	4 ms	848 KB	Output is correct
11	Correct	4 ms	848 KB	Output is correct
12	Correct	5 ms	868 KB	Output is correct
13	Correct	4 ms	868 KB	Output is correct
14	Correct	4 ms	868 KB	Output is correct
15	Correct	4 ms	868 KB	Output is correct
16	Correct	3 ms	868 KB	Output is correct
17	Correct	5 ms	868 KB	Output is correct
18	Correct	4 ms	868 KB	Output is correct
19	Correct	4 ms	868 KB	Output is correct
20	Correct	4 ms	868 KB	Output is correct
21	Correct	3 ms	868 KB	Output is correct
22	Correct	3 ms	868 KB	Output is correct
23	Correct	3 ms	868 KB	Output is correct
24	Correct	4 ms	868 KB	Output is correct
25	Correct	4 ms	868 KB	Output is correct
26	Correct	4 ms	868 KB	Output is correct
27	Correct	3 ms	868 KB	Output is correct
28	Correct	4 ms	868 KB	Output is correct
29	Correct	4 ms	868 KB	Output is correct
30	Correct	4 ms	868 KB	Output is correct
31	Correct	1162 ms	27932 KB	Output is correct
32	Correct	223 ms	27932 KB	Output is correct
33	Correct	1350 ms	29908 KB	Output is correct
34	Correct	1131 ms	30100 KB	Output is correct
35	Correct	1214 ms	30100 KB	Output is correct
36	Correct	1097 ms	30100 KB	Output is correct
37	Correct	904 ms	30260 KB	Output is correct
38	Correct	855 ms	31236 KB	Output is correct
39	Correct	607 ms	31236 KB	Output is correct
40	Correct	635 ms	31236 KB	Output is correct
41	Correct	651 ms	31236 KB	Output is correct
42	Correct	700 ms	31236 KB	Output is correct
43	Correct	47 ms	31236 KB	Output is correct
44	Correct	745 ms	31236 KB	Output is correct
45	Correct	735 ms	31236 KB	Output is correct
46	Correct	746 ms	31236 KB	Output is correct
47	Correct	430 ms	31236 KB	Output is correct
48	Correct	447 ms	31236 KB	Output is correct
49	Correct	536 ms	31236 KB	Output is correct
50	Correct	423 ms	31236 KB	Output is correct
51	Correct	506 ms	31236 KB	Output is correct
52	Correct	1037 ms	89936 KB	Output is correct
53	Correct	1002 ms	90228 KB	Output is correct
54	Correct	720 ms	90680 KB	Output is correct
55	Correct	785 ms	90680 KB	Output is correct
56	Correct	865 ms	124304 KB	Output is correct
57	Correct	794 ms	124304 KB	Output is correct
58	Correct	548 ms	124304 KB	Output is correct
59	Correct	656 ms	124304 KB	Output is correct
60	Correct	797 ms	124304 KB	Output is correct
61	Correct	986 ms	124304 KB	Output is correct
62	Correct	494 ms	124304 KB	Output is correct
63	Correct	492 ms	124304 KB	Output is correct
64	Execution timed out	5003 ms	132368 KB	Time limit exceeded
65	Halted	0 ms	0 KB	-

답안 #49703

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