답안 #49714 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
49714	2018-06-02T09:47:53 Z	SpaimaCarpatilor	새 집 (APIO18_new_home)	C++17	57 / 100	5000 ms	143700 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 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[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++)
        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:201: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	41 ms	49656 KB	Output is correct
2	Correct	45 ms	49768 KB	Output is correct
3	Correct	43 ms	49820 KB	Output is correct
4	Correct	47 ms	49844 KB	Output is correct
5	Correct	46 ms	49972 KB	Output is correct
6	Correct	47 ms	49972 KB	Output is correct
7	Correct	45 ms	49972 KB	Output is correct
8	Correct	54 ms	50028 KB	Output is correct
9	Correct	47 ms	50028 KB	Output is correct
10	Correct	52 ms	50160 KB	Output is correct
11	Correct	53 ms	50160 KB	Output is correct
12	Correct	57 ms	50176 KB	Output is correct
13	Correct	45 ms	50176 KB	Output is correct
14	Correct	55 ms	50176 KB	Output is correct
15	Correct	45 ms	50176 KB	Output is correct
16	Correct	41 ms	50176 KB	Output is correct
17	Correct	43 ms	50176 KB	Output is correct
18	Correct	43 ms	50176 KB	Output is correct
19	Correct	42 ms	50176 KB	Output is correct
20	Correct	41 ms	50176 KB	Output is correct
21	Correct	41 ms	50176 KB	Output is correct
22	Correct	43 ms	50176 KB	Output is correct
23	Correct	41 ms	50176 KB	Output is correct
24	Correct	41 ms	50176 KB	Output is correct
25	Correct	48 ms	50176 KB	Output is correct
26	Correct	55 ms	50176 KB	Output is correct
27	Correct	46 ms	50176 KB	Output is correct
28	Correct	45 ms	50176 KB	Output is correct
29	Correct	94 ms	50176 KB	Output is correct
30	Correct	45 ms	50180 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	41 ms	49656 KB	Output is correct
2	Correct	45 ms	49768 KB	Output is correct
3	Correct	43 ms	49820 KB	Output is correct
4	Correct	47 ms	49844 KB	Output is correct
5	Correct	46 ms	49972 KB	Output is correct
6	Correct	47 ms	49972 KB	Output is correct
7	Correct	45 ms	49972 KB	Output is correct
8	Correct	54 ms	50028 KB	Output is correct
9	Correct	47 ms	50028 KB	Output is correct
10	Correct	52 ms	50160 KB	Output is correct
11	Correct	53 ms	50160 KB	Output is correct
12	Correct	57 ms	50176 KB	Output is correct
13	Correct	45 ms	50176 KB	Output is correct
14	Correct	55 ms	50176 KB	Output is correct
15	Correct	45 ms	50176 KB	Output is correct
16	Correct	41 ms	50176 KB	Output is correct
17	Correct	43 ms	50176 KB	Output is correct
18	Correct	43 ms	50176 KB	Output is correct
19	Correct	42 ms	50176 KB	Output is correct
20	Correct	41 ms	50176 KB	Output is correct
21	Correct	41 ms	50176 KB	Output is correct
22	Correct	43 ms	50176 KB	Output is correct
23	Correct	41 ms	50176 KB	Output is correct
24	Correct	41 ms	50176 KB	Output is correct
25	Correct	48 ms	50176 KB	Output is correct
26	Correct	55 ms	50176 KB	Output is correct
27	Correct	46 ms	50176 KB	Output is correct
28	Correct	45 ms	50176 KB	Output is correct
29	Correct	94 ms	50176 KB	Output is correct
30	Correct	45 ms	50180 KB	Output is correct
31	Correct	1323 ms	70144 KB	Output is correct
32	Correct	259 ms	70144 KB	Output is correct
33	Correct	1207 ms	72272 KB	Output is correct
34	Correct	1008 ms	72596 KB	Output is correct
35	Correct	1205 ms	72596 KB	Output is correct
36	Correct	1308 ms	72596 KB	Output is correct
37	Correct	874 ms	72712 KB	Output is correct
38	Correct	952 ms	73452 KB	Output is correct
39	Correct	651 ms	73452 KB	Output is correct
40	Correct	673 ms	73452 KB	Output is correct
41	Correct	661 ms	73452 KB	Output is correct
42	Correct	592 ms	73452 KB	Output is correct
43	Correct	72 ms	73452 KB	Output is correct
44	Correct	659 ms	73452 KB	Output is correct
45	Correct	713 ms	73452 KB	Output is correct
46	Correct	768 ms	73452 KB	Output is correct
47	Correct	526 ms	73452 KB	Output is correct
48	Correct	519 ms	73452 KB	Output is correct
49	Correct	500 ms	73452 KB	Output is correct
50	Correct	443 ms	73452 KB	Output is correct
51	Correct	532 ms	73452 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	856 ms	101252 KB	Output is correct
2	Correct	1004 ms	104456 KB	Output is correct
3	Correct	783 ms	104456 KB	Output is correct
4	Correct	867 ms	104456 KB	Output is correct
5	Correct	1087 ms	143332 KB	Output is correct
6	Correct	1039 ms	143332 KB	Output is correct
7	Correct	647 ms	143332 KB	Output is correct
8	Correct	1030 ms	143332 KB	Output is correct
9	Correct	784 ms	143332 KB	Output is correct
10	Correct	835 ms	143332 KB	Output is correct
11	Correct	554 ms	143332 KB	Output is correct
12	Correct	613 ms	143332 KB	Output is correct

Subtask #4
0 / 23.0

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

Subtask #5
35.0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	41 ms	49656 KB	Output is correct
2	Correct	45 ms	49768 KB	Output is correct
3	Correct	43 ms	49820 KB	Output is correct
4	Correct	47 ms	49844 KB	Output is correct
5	Correct	46 ms	49972 KB	Output is correct
6	Correct	47 ms	49972 KB	Output is correct
7	Correct	45 ms	49972 KB	Output is correct
8	Correct	54 ms	50028 KB	Output is correct
9	Correct	47 ms	50028 KB	Output is correct
10	Correct	52 ms	50160 KB	Output is correct
11	Correct	53 ms	50160 KB	Output is correct
12	Correct	57 ms	50176 KB	Output is correct
13	Correct	45 ms	50176 KB	Output is correct
14	Correct	55 ms	50176 KB	Output is correct
15	Correct	45 ms	50176 KB	Output is correct
16	Correct	41 ms	50176 KB	Output is correct
17	Correct	43 ms	50176 KB	Output is correct
18	Correct	43 ms	50176 KB	Output is correct
19	Correct	42 ms	50176 KB	Output is correct
20	Correct	41 ms	50176 KB	Output is correct
21	Correct	41 ms	50176 KB	Output is correct
22	Correct	43 ms	50176 KB	Output is correct
23	Correct	41 ms	50176 KB	Output is correct
24	Correct	41 ms	50176 KB	Output is correct
25	Correct	48 ms	50176 KB	Output is correct
26	Correct	55 ms	50176 KB	Output is correct
27	Correct	46 ms	50176 KB	Output is correct
28	Correct	45 ms	50176 KB	Output is correct
29	Correct	94 ms	50176 KB	Output is correct
30	Correct	45 ms	50180 KB	Output is correct
31	Correct	1323 ms	70144 KB	Output is correct
32	Correct	259 ms	70144 KB	Output is correct
33	Correct	1207 ms	72272 KB	Output is correct
34	Correct	1008 ms	72596 KB	Output is correct
35	Correct	1205 ms	72596 KB	Output is correct
36	Correct	1308 ms	72596 KB	Output is correct
37	Correct	874 ms	72712 KB	Output is correct
38	Correct	952 ms	73452 KB	Output is correct
39	Correct	651 ms	73452 KB	Output is correct
40	Correct	673 ms	73452 KB	Output is correct
41	Correct	661 ms	73452 KB	Output is correct
42	Correct	592 ms	73452 KB	Output is correct
43	Correct	72 ms	73452 KB	Output is correct
44	Correct	659 ms	73452 KB	Output is correct
45	Correct	713 ms	73452 KB	Output is correct
46	Correct	768 ms	73452 KB	Output is correct
47	Correct	526 ms	73452 KB	Output is correct
48	Correct	519 ms	73452 KB	Output is correct
49	Correct	500 ms	73452 KB	Output is correct
50	Correct	443 ms	73452 KB	Output is correct
51	Correct	532 ms	73452 KB	Output is correct
52	Correct	539 ms	143700 KB	Output is correct
53	Correct	553 ms	143700 KB	Output is correct
54	Correct	801 ms	143700 KB	Output is correct
55	Correct	574 ms	143700 KB	Output is correct
56	Correct	422 ms	143700 KB	Output is correct
57	Correct	614 ms	143700 KB	Output is correct
58	Correct	507 ms	143700 KB	Output is correct
59	Correct	465 ms	143700 KB	Output is correct
60	Correct	582 ms	143700 KB	Output is correct
61	Correct	70 ms	143700 KB	Output is correct
62	Correct	404 ms	143700 KB	Output is correct
63	Correct	413 ms	143700 KB	Output is correct
64	Correct	562 ms	143700 KB	Output is correct
65	Correct	529 ms	143700 KB	Output is correct
66	Correct	621 ms	143700 KB	Output is correct
67	Correct	174 ms	143700 KB	Output is correct

Subtask #6
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	41 ms	49656 KB	Output is correct
2	Correct	45 ms	49768 KB	Output is correct
3	Correct	43 ms	49820 KB	Output is correct
4	Correct	47 ms	49844 KB	Output is correct
5	Correct	46 ms	49972 KB	Output is correct
6	Correct	47 ms	49972 KB	Output is correct
7	Correct	45 ms	49972 KB	Output is correct
8	Correct	54 ms	50028 KB	Output is correct
9	Correct	47 ms	50028 KB	Output is correct
10	Correct	52 ms	50160 KB	Output is correct
11	Correct	53 ms	50160 KB	Output is correct
12	Correct	57 ms	50176 KB	Output is correct
13	Correct	45 ms	50176 KB	Output is correct
14	Correct	55 ms	50176 KB	Output is correct
15	Correct	45 ms	50176 KB	Output is correct
16	Correct	41 ms	50176 KB	Output is correct
17	Correct	43 ms	50176 KB	Output is correct
18	Correct	43 ms	50176 KB	Output is correct
19	Correct	42 ms	50176 KB	Output is correct
20	Correct	41 ms	50176 KB	Output is correct
21	Correct	41 ms	50176 KB	Output is correct
22	Correct	43 ms	50176 KB	Output is correct
23	Correct	41 ms	50176 KB	Output is correct
24	Correct	41 ms	50176 KB	Output is correct
25	Correct	48 ms	50176 KB	Output is correct
26	Correct	55 ms	50176 KB	Output is correct
27	Correct	46 ms	50176 KB	Output is correct
28	Correct	45 ms	50176 KB	Output is correct
29	Correct	94 ms	50176 KB	Output is correct
30	Correct	45 ms	50180 KB	Output is correct
31	Correct	1323 ms	70144 KB	Output is correct
32	Correct	259 ms	70144 KB	Output is correct
33	Correct	1207 ms	72272 KB	Output is correct
34	Correct	1008 ms	72596 KB	Output is correct
35	Correct	1205 ms	72596 KB	Output is correct
36	Correct	1308 ms	72596 KB	Output is correct
37	Correct	874 ms	72712 KB	Output is correct
38	Correct	952 ms	73452 KB	Output is correct
39	Correct	651 ms	73452 KB	Output is correct
40	Correct	673 ms	73452 KB	Output is correct
41	Correct	661 ms	73452 KB	Output is correct
42	Correct	592 ms	73452 KB	Output is correct
43	Correct	72 ms	73452 KB	Output is correct
44	Correct	659 ms	73452 KB	Output is correct
45	Correct	713 ms	73452 KB	Output is correct
46	Correct	768 ms	73452 KB	Output is correct
47	Correct	526 ms	73452 KB	Output is correct
48	Correct	519 ms	73452 KB	Output is correct
49	Correct	500 ms	73452 KB	Output is correct
50	Correct	443 ms	73452 KB	Output is correct
51	Correct	532 ms	73452 KB	Output is correct
52	Correct	856 ms	101252 KB	Output is correct
53	Correct	1004 ms	104456 KB	Output is correct
54	Correct	783 ms	104456 KB	Output is correct
55	Correct	867 ms	104456 KB	Output is correct
56	Correct	1087 ms	143332 KB	Output is correct
57	Correct	1039 ms	143332 KB	Output is correct
58	Correct	647 ms	143332 KB	Output is correct
59	Correct	1030 ms	143332 KB	Output is correct
60	Correct	784 ms	143332 KB	Output is correct
61	Correct	835 ms	143332 KB	Output is correct
62	Correct	554 ms	143332 KB	Output is correct
63	Correct	613 ms	143332 KB	Output is correct
64	Execution timed out	5048 ms	143700 KB	Time limit exceeded
65	Halted	0 ms	0 KB	-

답안 #49714

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