답안 #49710 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
49710	2018-06-02T09:33:53 Z	SpaimaCarpatilor	새 집 (APIO18_new_home)	C++17	57 / 100	5000 ms	138016 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 > qry[300009];

void solveDC (int nod, int st, int dr, vector < int > &A, vector < int > &B)
{
    changesLine ++;
    int mij = (st + dr) >> 1;
    for (auto it : A)
        if (a[it] > dr)
            delPoint (type[it], x[it]);
    for (auto it : B)
        if (b[it] < st)
            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
    {
        vector < int > leftA, leftB, rightA, rightB;
        for (auto it : A)
            if (a[it] <= dr)
            {
                leftA.push_back (it);
                if (a[it] - 1 > mij) rightA.push_back (it);
            }
        for (auto it : B)
            if (b[it] >= st)
            {
                rightB.push_back (it);
                if (b[it] + 1 <= mij) leftB.push_back (it);
            }
        int f1 = nod << 1, f2 = f1 | 1;
        solveDC (f1, st, mij, leftA, leftB);
        solveDC (f2, mij + 1, dr, rightA, rightB);
    }
    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 ();
vector < int > initA, initB;
for (int i=1; i<=N; i++)
    if (a[i] <= b[i])
        initA.push_back (i),
        initB.push_back (i);
for (int i=1; i<=Q; i++)
    qry[when[i]].push_back (i);
solveDC (1, 1, timeCount, initA, initB);
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	23 ms	21500 KB	Output is correct
2	Correct	24 ms	21732 KB	Output is correct
3	Correct	21 ms	21732 KB	Output is correct
4	Correct	21 ms	21732 KB	Output is correct
5	Correct	21 ms	21732 KB	Output is correct
6	Correct	27 ms	21940 KB	Output is correct
7	Correct	26 ms	21940 KB	Output is correct
8	Correct	23 ms	21948 KB	Output is correct
9	Correct	22 ms	21948 KB	Output is correct
10	Correct	23 ms	21948 KB	Output is correct
11	Correct	25 ms	21948 KB	Output is correct
12	Correct	20 ms	21948 KB	Output is correct
13	Correct	19 ms	21948 KB	Output is correct
14	Correct	21 ms	21948 KB	Output is correct
15	Correct	21 ms	21948 KB	Output is correct
16	Correct	23 ms	21948 KB	Output is correct
17	Correct	22 ms	21948 KB	Output is correct
18	Correct	22 ms	21948 KB	Output is correct
19	Correct	22 ms	21996 KB	Output is correct
20	Correct	19 ms	21996 KB	Output is correct
21	Correct	21 ms	21996 KB	Output is correct
22	Correct	24 ms	21996 KB	Output is correct
23	Correct	20 ms	21996 KB	Output is correct
24	Correct	19 ms	21996 KB	Output is correct
25	Correct	20 ms	21996 KB	Output is correct
26	Correct	24 ms	21996 KB	Output is correct
27	Correct	21 ms	21996 KB	Output is correct
28	Correct	19 ms	21996 KB	Output is correct
29	Correct	21 ms	21996 KB	Output is correct
30	Correct	20 ms	21996 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	23 ms	21500 KB	Output is correct
2	Correct	24 ms	21732 KB	Output is correct
3	Correct	21 ms	21732 KB	Output is correct
4	Correct	21 ms	21732 KB	Output is correct
5	Correct	21 ms	21732 KB	Output is correct
6	Correct	27 ms	21940 KB	Output is correct
7	Correct	26 ms	21940 KB	Output is correct
8	Correct	23 ms	21948 KB	Output is correct
9	Correct	22 ms	21948 KB	Output is correct
10	Correct	23 ms	21948 KB	Output is correct
11	Correct	25 ms	21948 KB	Output is correct
12	Correct	20 ms	21948 KB	Output is correct
13	Correct	19 ms	21948 KB	Output is correct
14	Correct	21 ms	21948 KB	Output is correct
15	Correct	21 ms	21948 KB	Output is correct
16	Correct	23 ms	21948 KB	Output is correct
17	Correct	22 ms	21948 KB	Output is correct
18	Correct	22 ms	21948 KB	Output is correct
19	Correct	22 ms	21996 KB	Output is correct
20	Correct	19 ms	21996 KB	Output is correct
21	Correct	21 ms	21996 KB	Output is correct
22	Correct	24 ms	21996 KB	Output is correct
23	Correct	20 ms	21996 KB	Output is correct
24	Correct	19 ms	21996 KB	Output is correct
25	Correct	20 ms	21996 KB	Output is correct
26	Correct	24 ms	21996 KB	Output is correct
27	Correct	21 ms	21996 KB	Output is correct
28	Correct	19 ms	21996 KB	Output is correct
29	Correct	21 ms	21996 KB	Output is correct
30	Correct	20 ms	21996 KB	Output is correct
31	Correct	975 ms	38288 KB	Output is correct
32	Correct	216 ms	38288 KB	Output is correct
33	Correct	1342 ms	40200 KB	Output is correct
34	Correct	1234 ms	40200 KB	Output is correct
35	Correct	1315 ms	40200 KB	Output is correct
36	Correct	1163 ms	40200 KB	Output is correct
37	Correct	865 ms	40200 KB	Output is correct
38	Correct	932 ms	40340 KB	Output is correct
39	Correct	789 ms	40340 KB	Output is correct
40	Correct	719 ms	40340 KB	Output is correct
41	Correct	696 ms	40340 KB	Output is correct
42	Correct	641 ms	40340 KB	Output is correct
43	Correct	58 ms	40340 KB	Output is correct
44	Correct	711 ms	40340 KB	Output is correct
45	Correct	728 ms	40340 KB	Output is correct
46	Correct	930 ms	40340 KB	Output is correct
47	Correct	497 ms	40340 KB	Output is correct
48	Correct	481 ms	40340 KB	Output is correct
49	Correct	511 ms	40340 KB	Output is correct
50	Correct	458 ms	40340 KB	Output is correct
51	Correct	550 ms	40340 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	909 ms	98692 KB	Output is correct
2	Correct	1008 ms	102992 KB	Output is correct
3	Correct	858 ms	102992 KB	Output is correct
4	Correct	877 ms	102992 KB	Output is correct
5	Correct	960 ms	138016 KB	Output is correct
6	Correct	1049 ms	138016 KB	Output is correct
7	Correct	856 ms	138016 KB	Output is correct
8	Correct	846 ms	138016 KB	Output is correct
9	Correct	727 ms	138016 KB	Output is correct
10	Correct	860 ms	138016 KB	Output is correct
11	Correct	499 ms	138016 KB	Output is correct
12	Correct	554 ms	138016 KB	Output is correct

Subtask #4
0 / 23.0

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

Subtask #5
35.0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	23 ms	21500 KB	Output is correct
2	Correct	24 ms	21732 KB	Output is correct
3	Correct	21 ms	21732 KB	Output is correct
4	Correct	21 ms	21732 KB	Output is correct
5	Correct	21 ms	21732 KB	Output is correct
6	Correct	27 ms	21940 KB	Output is correct
7	Correct	26 ms	21940 KB	Output is correct
8	Correct	23 ms	21948 KB	Output is correct
9	Correct	22 ms	21948 KB	Output is correct
10	Correct	23 ms	21948 KB	Output is correct
11	Correct	25 ms	21948 KB	Output is correct
12	Correct	20 ms	21948 KB	Output is correct
13	Correct	19 ms	21948 KB	Output is correct
14	Correct	21 ms	21948 KB	Output is correct
15	Correct	21 ms	21948 KB	Output is correct
16	Correct	23 ms	21948 KB	Output is correct
17	Correct	22 ms	21948 KB	Output is correct
18	Correct	22 ms	21948 KB	Output is correct
19	Correct	22 ms	21996 KB	Output is correct
20	Correct	19 ms	21996 KB	Output is correct
21	Correct	21 ms	21996 KB	Output is correct
22	Correct	24 ms	21996 KB	Output is correct
23	Correct	20 ms	21996 KB	Output is correct
24	Correct	19 ms	21996 KB	Output is correct
25	Correct	20 ms	21996 KB	Output is correct
26	Correct	24 ms	21996 KB	Output is correct
27	Correct	21 ms	21996 KB	Output is correct
28	Correct	19 ms	21996 KB	Output is correct
29	Correct	21 ms	21996 KB	Output is correct
30	Correct	20 ms	21996 KB	Output is correct
31	Correct	975 ms	38288 KB	Output is correct
32	Correct	216 ms	38288 KB	Output is correct
33	Correct	1342 ms	40200 KB	Output is correct
34	Correct	1234 ms	40200 KB	Output is correct
35	Correct	1315 ms	40200 KB	Output is correct
36	Correct	1163 ms	40200 KB	Output is correct
37	Correct	865 ms	40200 KB	Output is correct
38	Correct	932 ms	40340 KB	Output is correct
39	Correct	789 ms	40340 KB	Output is correct
40	Correct	719 ms	40340 KB	Output is correct
41	Correct	696 ms	40340 KB	Output is correct
42	Correct	641 ms	40340 KB	Output is correct
43	Correct	58 ms	40340 KB	Output is correct
44	Correct	711 ms	40340 KB	Output is correct
45	Correct	728 ms	40340 KB	Output is correct
46	Correct	930 ms	40340 KB	Output is correct
47	Correct	497 ms	40340 KB	Output is correct
48	Correct	481 ms	40340 KB	Output is correct
49	Correct	511 ms	40340 KB	Output is correct
50	Correct	458 ms	40340 KB	Output is correct
51	Correct	550 ms	40340 KB	Output is correct
52	Correct	379 ms	138016 KB	Output is correct
53	Correct	431 ms	138016 KB	Output is correct
54	Correct	541 ms	138016 KB	Output is correct
55	Correct	527 ms	138016 KB	Output is correct
56	Correct	468 ms	138016 KB	Output is correct
57	Correct	670 ms	138016 KB	Output is correct
58	Correct	595 ms	138016 KB	Output is correct
59	Correct	525 ms	138016 KB	Output is correct
60	Correct	699 ms	138016 KB	Output is correct
61	Correct	48 ms	138016 KB	Output is correct
62	Correct	422 ms	138016 KB	Output is correct
63	Correct	664 ms	138016 KB	Output is correct
64	Correct	517 ms	138016 KB	Output is correct
65	Correct	495 ms	138016 KB	Output is correct
66	Correct	555 ms	138016 KB	Output is correct
67	Correct	152 ms	138016 KB	Output is correct

Subtask #6
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	23 ms	21500 KB	Output is correct
2	Correct	24 ms	21732 KB	Output is correct
3	Correct	21 ms	21732 KB	Output is correct
4	Correct	21 ms	21732 KB	Output is correct
5	Correct	21 ms	21732 KB	Output is correct
6	Correct	27 ms	21940 KB	Output is correct
7	Correct	26 ms	21940 KB	Output is correct
8	Correct	23 ms	21948 KB	Output is correct
9	Correct	22 ms	21948 KB	Output is correct
10	Correct	23 ms	21948 KB	Output is correct
11	Correct	25 ms	21948 KB	Output is correct
12	Correct	20 ms	21948 KB	Output is correct
13	Correct	19 ms	21948 KB	Output is correct
14	Correct	21 ms	21948 KB	Output is correct
15	Correct	21 ms	21948 KB	Output is correct
16	Correct	23 ms	21948 KB	Output is correct
17	Correct	22 ms	21948 KB	Output is correct
18	Correct	22 ms	21948 KB	Output is correct
19	Correct	22 ms	21996 KB	Output is correct
20	Correct	19 ms	21996 KB	Output is correct
21	Correct	21 ms	21996 KB	Output is correct
22	Correct	24 ms	21996 KB	Output is correct
23	Correct	20 ms	21996 KB	Output is correct
24	Correct	19 ms	21996 KB	Output is correct
25	Correct	20 ms	21996 KB	Output is correct
26	Correct	24 ms	21996 KB	Output is correct
27	Correct	21 ms	21996 KB	Output is correct
28	Correct	19 ms	21996 KB	Output is correct
29	Correct	21 ms	21996 KB	Output is correct
30	Correct	20 ms	21996 KB	Output is correct
31	Correct	975 ms	38288 KB	Output is correct
32	Correct	216 ms	38288 KB	Output is correct
33	Correct	1342 ms	40200 KB	Output is correct
34	Correct	1234 ms	40200 KB	Output is correct
35	Correct	1315 ms	40200 KB	Output is correct
36	Correct	1163 ms	40200 KB	Output is correct
37	Correct	865 ms	40200 KB	Output is correct
38	Correct	932 ms	40340 KB	Output is correct
39	Correct	789 ms	40340 KB	Output is correct
40	Correct	719 ms	40340 KB	Output is correct
41	Correct	696 ms	40340 KB	Output is correct
42	Correct	641 ms	40340 KB	Output is correct
43	Correct	58 ms	40340 KB	Output is correct
44	Correct	711 ms	40340 KB	Output is correct
45	Correct	728 ms	40340 KB	Output is correct
46	Correct	930 ms	40340 KB	Output is correct
47	Correct	497 ms	40340 KB	Output is correct
48	Correct	481 ms	40340 KB	Output is correct
49	Correct	511 ms	40340 KB	Output is correct
50	Correct	458 ms	40340 KB	Output is correct
51	Correct	550 ms	40340 KB	Output is correct
52	Correct	909 ms	98692 KB	Output is correct
53	Correct	1008 ms	102992 KB	Output is correct
54	Correct	858 ms	102992 KB	Output is correct
55	Correct	877 ms	102992 KB	Output is correct
56	Correct	960 ms	138016 KB	Output is correct
57	Correct	1049 ms	138016 KB	Output is correct
58	Correct	856 ms	138016 KB	Output is correct
59	Correct	846 ms	138016 KB	Output is correct
60	Correct	727 ms	138016 KB	Output is correct
61	Correct	860 ms	138016 KB	Output is correct
62	Correct	499 ms	138016 KB	Output is correct
63	Correct	554 ms	138016 KB	Output is correct
64	Execution timed out	5028 ms	138016 KB	Time limit exceeded
65	Halted	0 ms	0 KB	-

답안 #49710

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