답안 #49702 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
49702	2018-06-02T08:58:13 Z	SpaimaCarpatilor	새 집 (APIO18_new_home)	C++17	57 / 100	5000 ms	129616 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 addLine (int type, int bg, int nd)
{
    int x = firstBigger (bg - 1), y = lastSmaller (nd + 1);
    if (x <= y)
    {
        if (type == 0) update (0, xCount - y + 1, -bg);
        else update (1, x, nd);
    }
}

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<=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:255: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	384 KB	Output is correct
3	Correct	3 ms	556 KB	Output is correct
4	Correct	2 ms	556 KB	Output is correct
5	Correct	3 ms	556 KB	Output is correct
6	Correct	5 ms	664 KB	Output is correct
7	Correct	4 ms	664 KB	Output is correct
8	Correct	4 ms	792 KB	Output is correct
9	Correct	5 ms	792 KB	Output is correct
10	Correct	4 ms	868 KB	Output is correct
11	Correct	5 ms	868 KB	Output is correct
12	Correct	6 ms	868 KB	Output is correct
13	Correct	4 ms	868 KB	Output is correct
14	Correct	3 ms	868 KB	Output is correct
15	Correct	5 ms	868 KB	Output is correct
16	Correct	4 ms	868 KB	Output is correct
17	Correct	6 ms	868 KB	Output is correct
18	Correct	5 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	2 ms	868 KB	Output is correct
22	Correct	5 ms	868 KB	Output is correct
23	Correct	4 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	6 ms	868 KB	Output is correct
27	Correct	4 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	3 ms	872 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	384 KB	Output is correct
3	Correct	3 ms	556 KB	Output is correct
4	Correct	2 ms	556 KB	Output is correct
5	Correct	3 ms	556 KB	Output is correct
6	Correct	5 ms	664 KB	Output is correct
7	Correct	4 ms	664 KB	Output is correct
8	Correct	4 ms	792 KB	Output is correct
9	Correct	5 ms	792 KB	Output is correct
10	Correct	4 ms	868 KB	Output is correct
11	Correct	5 ms	868 KB	Output is correct
12	Correct	6 ms	868 KB	Output is correct
13	Correct	4 ms	868 KB	Output is correct
14	Correct	3 ms	868 KB	Output is correct
15	Correct	5 ms	868 KB	Output is correct
16	Correct	4 ms	868 KB	Output is correct
17	Correct	6 ms	868 KB	Output is correct
18	Correct	5 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	2 ms	868 KB	Output is correct
22	Correct	5 ms	868 KB	Output is correct
23	Correct	4 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	6 ms	868 KB	Output is correct
27	Correct	4 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	3 ms	872 KB	Output is correct
31	Correct	1316 ms	27708 KB	Output is correct
32	Correct	179 ms	27708 KB	Output is correct
33	Correct	1524 ms	29604 KB	Output is correct
34	Correct	1508 ms	30084 KB	Output is correct
35	Correct	1702 ms	30084 KB	Output is correct
36	Correct	1581 ms	30084 KB	Output is correct
37	Correct	1097 ms	30172 KB	Output is correct
38	Correct	1220 ms	30172 KB	Output is correct
39	Correct	812 ms	30172 KB	Output is correct
40	Correct	855 ms	30172 KB	Output is correct
41	Correct	1060 ms	30172 KB	Output is correct
42	Correct	999 ms	30172 KB	Output is correct
43	Correct	38 ms	30172 KB	Output is correct
44	Correct	1068 ms	30172 KB	Output is correct
45	Correct	1076 ms	30172 KB	Output is correct
46	Correct	1204 ms	30172 KB	Output is correct
47	Correct	581 ms	30172 KB	Output is correct
48	Correct	599 ms	30172 KB	Output is correct
49	Correct	741 ms	30172 KB	Output is correct
50	Correct	619 ms	30172 KB	Output is correct
51	Correct	732 ms	30172 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1052 ms	89868 KB	Output is correct
2	Correct	1093 ms	89868 KB	Output is correct
3	Correct	814 ms	90568 KB	Output is correct
4	Correct	1064 ms	90704 KB	Output is correct
5	Correct	932 ms	92840 KB	Output is correct
6	Correct	1114 ms	92840 KB	Output is correct
7	Correct	821 ms	92840 KB	Output is correct
8	Correct	1002 ms	92840 KB	Output is correct
9	Correct	1018 ms	92840 KB	Output is correct
10	Correct	950 ms	92840 KB	Output is correct
11	Correct	581 ms	92840 KB	Output is correct
12	Correct	664 ms	92840 KB	Output is correct

Subtask #4
0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	5013 ms	129616 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	384 KB	Output is correct
3	Correct	3 ms	556 KB	Output is correct
4	Correct	2 ms	556 KB	Output is correct
5	Correct	3 ms	556 KB	Output is correct
6	Correct	5 ms	664 KB	Output is correct
7	Correct	4 ms	664 KB	Output is correct
8	Correct	4 ms	792 KB	Output is correct
9	Correct	5 ms	792 KB	Output is correct
10	Correct	4 ms	868 KB	Output is correct
11	Correct	5 ms	868 KB	Output is correct
12	Correct	6 ms	868 KB	Output is correct
13	Correct	4 ms	868 KB	Output is correct
14	Correct	3 ms	868 KB	Output is correct
15	Correct	5 ms	868 KB	Output is correct
16	Correct	4 ms	868 KB	Output is correct
17	Correct	6 ms	868 KB	Output is correct
18	Correct	5 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	2 ms	868 KB	Output is correct
22	Correct	5 ms	868 KB	Output is correct
23	Correct	4 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	6 ms	868 KB	Output is correct
27	Correct	4 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	3 ms	872 KB	Output is correct
31	Correct	1316 ms	27708 KB	Output is correct
32	Correct	179 ms	27708 KB	Output is correct
33	Correct	1524 ms	29604 KB	Output is correct
34	Correct	1508 ms	30084 KB	Output is correct
35	Correct	1702 ms	30084 KB	Output is correct
36	Correct	1581 ms	30084 KB	Output is correct
37	Correct	1097 ms	30172 KB	Output is correct
38	Correct	1220 ms	30172 KB	Output is correct
39	Correct	812 ms	30172 KB	Output is correct
40	Correct	855 ms	30172 KB	Output is correct
41	Correct	1060 ms	30172 KB	Output is correct
42	Correct	999 ms	30172 KB	Output is correct
43	Correct	38 ms	30172 KB	Output is correct
44	Correct	1068 ms	30172 KB	Output is correct
45	Correct	1076 ms	30172 KB	Output is correct
46	Correct	1204 ms	30172 KB	Output is correct
47	Correct	581 ms	30172 KB	Output is correct
48	Correct	599 ms	30172 KB	Output is correct
49	Correct	741 ms	30172 KB	Output is correct
50	Correct	619 ms	30172 KB	Output is correct
51	Correct	732 ms	30172 KB	Output is correct
52	Correct	594 ms	129616 KB	Output is correct
53	Correct	466 ms	129616 KB	Output is correct
54	Correct	743 ms	129616 KB	Output is correct
55	Correct	726 ms	129616 KB	Output is correct
56	Correct	773 ms	129616 KB	Output is correct
57	Correct	951 ms	129616 KB	Output is correct
58	Correct	880 ms	129616 KB	Output is correct
59	Correct	735 ms	129616 KB	Output is correct
60	Correct	1030 ms	129616 KB	Output is correct
61	Correct	34 ms	129616 KB	Output is correct
62	Correct	530 ms	129616 KB	Output is correct
63	Correct	821 ms	129616 KB	Output is correct
64	Correct	791 ms	129616 KB	Output is correct
65	Correct	985 ms	129616 KB	Output is correct
66	Correct	995 ms	129616 KB	Output is correct
67	Correct	156 ms	129616 KB	Output is correct

Subtask #6
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	384 KB	Output is correct
3	Correct	3 ms	556 KB	Output is correct
4	Correct	2 ms	556 KB	Output is correct
5	Correct	3 ms	556 KB	Output is correct
6	Correct	5 ms	664 KB	Output is correct
7	Correct	4 ms	664 KB	Output is correct
8	Correct	4 ms	792 KB	Output is correct
9	Correct	5 ms	792 KB	Output is correct
10	Correct	4 ms	868 KB	Output is correct
11	Correct	5 ms	868 KB	Output is correct
12	Correct	6 ms	868 KB	Output is correct
13	Correct	4 ms	868 KB	Output is correct
14	Correct	3 ms	868 KB	Output is correct
15	Correct	5 ms	868 KB	Output is correct
16	Correct	4 ms	868 KB	Output is correct
17	Correct	6 ms	868 KB	Output is correct
18	Correct	5 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	2 ms	868 KB	Output is correct
22	Correct	5 ms	868 KB	Output is correct
23	Correct	4 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	6 ms	868 KB	Output is correct
27	Correct	4 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	3 ms	872 KB	Output is correct
31	Correct	1316 ms	27708 KB	Output is correct
32	Correct	179 ms	27708 KB	Output is correct
33	Correct	1524 ms	29604 KB	Output is correct
34	Correct	1508 ms	30084 KB	Output is correct
35	Correct	1702 ms	30084 KB	Output is correct
36	Correct	1581 ms	30084 KB	Output is correct
37	Correct	1097 ms	30172 KB	Output is correct
38	Correct	1220 ms	30172 KB	Output is correct
39	Correct	812 ms	30172 KB	Output is correct
40	Correct	855 ms	30172 KB	Output is correct
41	Correct	1060 ms	30172 KB	Output is correct
42	Correct	999 ms	30172 KB	Output is correct
43	Correct	38 ms	30172 KB	Output is correct
44	Correct	1068 ms	30172 KB	Output is correct
45	Correct	1076 ms	30172 KB	Output is correct
46	Correct	1204 ms	30172 KB	Output is correct
47	Correct	581 ms	30172 KB	Output is correct
48	Correct	599 ms	30172 KB	Output is correct
49	Correct	741 ms	30172 KB	Output is correct
50	Correct	619 ms	30172 KB	Output is correct
51	Correct	732 ms	30172 KB	Output is correct
52	Correct	1052 ms	89868 KB	Output is correct
53	Correct	1093 ms	89868 KB	Output is correct
54	Correct	814 ms	90568 KB	Output is correct
55	Correct	1064 ms	90704 KB	Output is correct
56	Correct	932 ms	92840 KB	Output is correct
57	Correct	1114 ms	92840 KB	Output is correct
58	Correct	821 ms	92840 KB	Output is correct
59	Correct	1002 ms	92840 KB	Output is correct
60	Correct	1018 ms	92840 KB	Output is correct
61	Correct	950 ms	92840 KB	Output is correct
62	Correct	581 ms	92840 KB	Output is correct
63	Correct	664 ms	92840 KB	Output is correct
64	Execution timed out	5013 ms	129616 KB	Time limit exceeded
65	Halted	0 ms	0 KB	-

답안 #49702

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