답안 #49651 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
49651	2018-06-01T15:44:03 Z	SpaimaCarpatilor	새 집 (APIO18_new_home)	C++17	57 / 100	5000 ms	230712 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 = 1200009;
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 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, 1, 1, xCount, x);
    int v2 = query (1, 1, 1, xCount, x);
    return max (v1, v2);
}

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)
{
    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]];
}

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] > 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);
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, 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 ();
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:231: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	380 KB	Output is correct
2	Correct	2 ms	488 KB	Output is correct
3	Correct	3 ms	488 KB	Output is correct
4	Correct	2 ms	488 KB	Output is correct
5	Correct	3 ms	608 KB	Output is correct
6	Correct	7 ms	1048 KB	Output is correct
7	Correct	4 ms	1048 KB	Output is correct
8	Correct	6 ms	1048 KB	Output is correct
9	Correct	4 ms	1048 KB	Output is correct
10	Correct	8 ms	1080 KB	Output is correct
11	Correct	7 ms	1080 KB	Output is correct
12	Correct	9 ms	1080 KB	Output is correct
13	Correct	5 ms	1084 KB	Output is correct
14	Correct	6 ms	1108 KB	Output is correct
15	Correct	5 ms	1108 KB	Output is correct
16	Correct	5 ms	1108 KB	Output is correct
17	Correct	6 ms	1108 KB	Output is correct
18	Correct	6 ms	1108 KB	Output is correct
19	Correct	5 ms	1108 KB	Output is correct
20	Correct	6 ms	1108 KB	Output is correct
21	Correct	3 ms	1108 KB	Output is correct
22	Correct	4 ms	1108 KB	Output is correct
23	Correct	5 ms	1108 KB	Output is correct
24	Correct	5 ms	1108 KB	Output is correct
25	Correct	8 ms	1152 KB	Output is correct
26	Correct	9 ms	1152 KB	Output is correct
27	Correct	4 ms	1152 KB	Output is correct
28	Correct	7 ms	1152 KB	Output is correct
29	Correct	6 ms	1152 KB	Output is correct
30	Correct	6 ms	1152 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	380 KB	Output is correct
2	Correct	2 ms	488 KB	Output is correct
3	Correct	3 ms	488 KB	Output is correct
4	Correct	2 ms	488 KB	Output is correct
5	Correct	3 ms	608 KB	Output is correct
6	Correct	7 ms	1048 KB	Output is correct
7	Correct	4 ms	1048 KB	Output is correct
8	Correct	6 ms	1048 KB	Output is correct
9	Correct	4 ms	1048 KB	Output is correct
10	Correct	8 ms	1080 KB	Output is correct
11	Correct	7 ms	1080 KB	Output is correct
12	Correct	9 ms	1080 KB	Output is correct
13	Correct	5 ms	1084 KB	Output is correct
14	Correct	6 ms	1108 KB	Output is correct
15	Correct	5 ms	1108 KB	Output is correct
16	Correct	5 ms	1108 KB	Output is correct
17	Correct	6 ms	1108 KB	Output is correct
18	Correct	6 ms	1108 KB	Output is correct
19	Correct	5 ms	1108 KB	Output is correct
20	Correct	6 ms	1108 KB	Output is correct
21	Correct	3 ms	1108 KB	Output is correct
22	Correct	4 ms	1108 KB	Output is correct
23	Correct	5 ms	1108 KB	Output is correct
24	Correct	5 ms	1108 KB	Output is correct
25	Correct	8 ms	1152 KB	Output is correct
26	Correct	9 ms	1152 KB	Output is correct
27	Correct	4 ms	1152 KB	Output is correct
28	Correct	7 ms	1152 KB	Output is correct
29	Correct	6 ms	1152 KB	Output is correct
30	Correct	6 ms	1152 KB	Output is correct
31	Correct	3407 ms	75448 KB	Output is correct
32	Correct	180 ms	75448 KB	Output is correct
33	Correct	3537 ms	75448 KB	Output is correct
34	Correct	3708 ms	80248 KB	Output is correct
35	Correct	3760 ms	80248 KB	Output is correct
36	Correct	3112 ms	80248 KB	Output is correct
37	Correct	2520 ms	80248 KB	Output is correct
38	Correct	2372 ms	80248 KB	Output is correct
39	Correct	1819 ms	80248 KB	Output is correct
40	Correct	1867 ms	80248 KB	Output is correct
41	Correct	2988 ms	80248 KB	Output is correct
42	Correct	2593 ms	80248 KB	Output is correct
43	Correct	30 ms	80248 KB	Output is correct
44	Correct	2699 ms	80248 KB	Output is correct
45	Correct	3009 ms	80248 KB	Output is correct
46	Correct	3302 ms	80248 KB	Output is correct
47	Correct	1402 ms	80248 KB	Output is correct
48	Correct	1542 ms	80248 KB	Output is correct
49	Correct	1820 ms	80248 KB	Output is correct
50	Correct	1708 ms	80248 KB	Output is correct
51	Correct	1911 ms	80248 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2952 ms	154280 KB	Output is correct
2	Correct	2786 ms	154280 KB	Output is correct
3	Correct	2902 ms	154280 KB	Output is correct
4	Correct	3371 ms	154280 KB	Output is correct
5	Correct	2669 ms	154280 KB	Output is correct
6	Correct	2515 ms	154280 KB	Output is correct
7	Correct	2189 ms	155188 KB	Output is correct
8	Correct	2785 ms	155188 KB	Output is correct
9	Correct	2820 ms	155188 KB	Output is correct
10	Correct	2667 ms	155188 KB	Output is correct
11	Correct	1143 ms	155188 KB	Output is correct
12	Correct	1402 ms	155188 KB	Output is correct

Subtask #4
0 / 23.0

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

Subtask #5
35.0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	380 KB	Output is correct
2	Correct	2 ms	488 KB	Output is correct
3	Correct	3 ms	488 KB	Output is correct
4	Correct	2 ms	488 KB	Output is correct
5	Correct	3 ms	608 KB	Output is correct
6	Correct	7 ms	1048 KB	Output is correct
7	Correct	4 ms	1048 KB	Output is correct
8	Correct	6 ms	1048 KB	Output is correct
9	Correct	4 ms	1048 KB	Output is correct
10	Correct	8 ms	1080 KB	Output is correct
11	Correct	7 ms	1080 KB	Output is correct
12	Correct	9 ms	1080 KB	Output is correct
13	Correct	5 ms	1084 KB	Output is correct
14	Correct	6 ms	1108 KB	Output is correct
15	Correct	5 ms	1108 KB	Output is correct
16	Correct	5 ms	1108 KB	Output is correct
17	Correct	6 ms	1108 KB	Output is correct
18	Correct	6 ms	1108 KB	Output is correct
19	Correct	5 ms	1108 KB	Output is correct
20	Correct	6 ms	1108 KB	Output is correct
21	Correct	3 ms	1108 KB	Output is correct
22	Correct	4 ms	1108 KB	Output is correct
23	Correct	5 ms	1108 KB	Output is correct
24	Correct	5 ms	1108 KB	Output is correct
25	Correct	8 ms	1152 KB	Output is correct
26	Correct	9 ms	1152 KB	Output is correct
27	Correct	4 ms	1152 KB	Output is correct
28	Correct	7 ms	1152 KB	Output is correct
29	Correct	6 ms	1152 KB	Output is correct
30	Correct	6 ms	1152 KB	Output is correct
31	Correct	3407 ms	75448 KB	Output is correct
32	Correct	180 ms	75448 KB	Output is correct
33	Correct	3537 ms	75448 KB	Output is correct
34	Correct	3708 ms	80248 KB	Output is correct
35	Correct	3760 ms	80248 KB	Output is correct
36	Correct	3112 ms	80248 KB	Output is correct
37	Correct	2520 ms	80248 KB	Output is correct
38	Correct	2372 ms	80248 KB	Output is correct
39	Correct	1819 ms	80248 KB	Output is correct
40	Correct	1867 ms	80248 KB	Output is correct
41	Correct	2988 ms	80248 KB	Output is correct
42	Correct	2593 ms	80248 KB	Output is correct
43	Correct	30 ms	80248 KB	Output is correct
44	Correct	2699 ms	80248 KB	Output is correct
45	Correct	3009 ms	80248 KB	Output is correct
46	Correct	3302 ms	80248 KB	Output is correct
47	Correct	1402 ms	80248 KB	Output is correct
48	Correct	1542 ms	80248 KB	Output is correct
49	Correct	1820 ms	80248 KB	Output is correct
50	Correct	1708 ms	80248 KB	Output is correct
51	Correct	1911 ms	80248 KB	Output is correct
52	Correct	1277 ms	230712 KB	Output is correct
53	Correct	1261 ms	230712 KB	Output is correct
54	Correct	1921 ms	230712 KB	Output is correct
55	Correct	1792 ms	230712 KB	Output is correct
56	Correct	1657 ms	230712 KB	Output is correct
57	Correct	2166 ms	230712 KB	Output is correct
58	Correct	1981 ms	230712 KB	Output is correct
59	Correct	1563 ms	230712 KB	Output is correct
60	Correct	2017 ms	230712 KB	Output is correct
61	Correct	28 ms	230712 KB	Output is correct
62	Correct	922 ms	230712 KB	Output is correct
63	Correct	1271 ms	230712 KB	Output is correct
64	Correct	1624 ms	230712 KB	Output is correct
65	Correct	2252 ms	230712 KB	Output is correct
66	Correct	2757 ms	230712 KB	Output is correct
67	Correct	236 ms	230712 KB	Output is correct

Subtask #6
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	380 KB	Output is correct
2	Correct	2 ms	488 KB	Output is correct
3	Correct	3 ms	488 KB	Output is correct
4	Correct	2 ms	488 KB	Output is correct
5	Correct	3 ms	608 KB	Output is correct
6	Correct	7 ms	1048 KB	Output is correct
7	Correct	4 ms	1048 KB	Output is correct
8	Correct	6 ms	1048 KB	Output is correct
9	Correct	4 ms	1048 KB	Output is correct
10	Correct	8 ms	1080 KB	Output is correct
11	Correct	7 ms	1080 KB	Output is correct
12	Correct	9 ms	1080 KB	Output is correct
13	Correct	5 ms	1084 KB	Output is correct
14	Correct	6 ms	1108 KB	Output is correct
15	Correct	5 ms	1108 KB	Output is correct
16	Correct	5 ms	1108 KB	Output is correct
17	Correct	6 ms	1108 KB	Output is correct
18	Correct	6 ms	1108 KB	Output is correct
19	Correct	5 ms	1108 KB	Output is correct
20	Correct	6 ms	1108 KB	Output is correct
21	Correct	3 ms	1108 KB	Output is correct
22	Correct	4 ms	1108 KB	Output is correct
23	Correct	5 ms	1108 KB	Output is correct
24	Correct	5 ms	1108 KB	Output is correct
25	Correct	8 ms	1152 KB	Output is correct
26	Correct	9 ms	1152 KB	Output is correct
27	Correct	4 ms	1152 KB	Output is correct
28	Correct	7 ms	1152 KB	Output is correct
29	Correct	6 ms	1152 KB	Output is correct
30	Correct	6 ms	1152 KB	Output is correct
31	Correct	3407 ms	75448 KB	Output is correct
32	Correct	180 ms	75448 KB	Output is correct
33	Correct	3537 ms	75448 KB	Output is correct
34	Correct	3708 ms	80248 KB	Output is correct
35	Correct	3760 ms	80248 KB	Output is correct
36	Correct	3112 ms	80248 KB	Output is correct
37	Correct	2520 ms	80248 KB	Output is correct
38	Correct	2372 ms	80248 KB	Output is correct
39	Correct	1819 ms	80248 KB	Output is correct
40	Correct	1867 ms	80248 KB	Output is correct
41	Correct	2988 ms	80248 KB	Output is correct
42	Correct	2593 ms	80248 KB	Output is correct
43	Correct	30 ms	80248 KB	Output is correct
44	Correct	2699 ms	80248 KB	Output is correct
45	Correct	3009 ms	80248 KB	Output is correct
46	Correct	3302 ms	80248 KB	Output is correct
47	Correct	1402 ms	80248 KB	Output is correct
48	Correct	1542 ms	80248 KB	Output is correct
49	Correct	1820 ms	80248 KB	Output is correct
50	Correct	1708 ms	80248 KB	Output is correct
51	Correct	1911 ms	80248 KB	Output is correct
52	Correct	2952 ms	154280 KB	Output is correct
53	Correct	2786 ms	154280 KB	Output is correct
54	Correct	2902 ms	154280 KB	Output is correct
55	Correct	3371 ms	154280 KB	Output is correct
56	Correct	2669 ms	154280 KB	Output is correct
57	Correct	2515 ms	154280 KB	Output is correct
58	Correct	2189 ms	155188 KB	Output is correct
59	Correct	2785 ms	155188 KB	Output is correct
60	Correct	2820 ms	155188 KB	Output is correct
61	Correct	2667 ms	155188 KB	Output is correct
62	Correct	1143 ms	155188 KB	Output is correct
63	Correct	1402 ms	155188 KB	Output is correct
64	Execution timed out	5049 ms	230712 KB	Time limit exceeded
65	Halted	0 ms	0 KB	-

답안 #49651

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