답안 #49642 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
49642	2018-06-01T14:12:25 Z	SpaimaCarpatilor	새 집 (APIO18_new_home)	C++17	5 / 100	5000 ms	1048576 KB

new_home

#include<bits/stdc++.h>

using namespace std;

int N, K, Q, timeCount, x[300009], type[300009], a[300009], b[300009], location[300009], when[300009], ans[300009];
const int INF = 5e8, maxX = 1e8;
int changesLine = 0;
vector < pair < int*, int > > changes[20];
vector < multiset < int > > S;
vector < pair < int, int > > setChanges[20];

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 = 8000009;
int cntNodes[2], aint[2][maxSize], leftSon[2][maxSize], rightSon[2][maxSize];
void update (int lin, int nod, int st, int dr, int x, int y, int lazyVal)
{
    if (nod == 1)
    {
        if (x < 1)
        {
            if (lin == 0) lazyVal += 1 - x;
            else lazyVal -= (1 - x);
            x = 1;
        }
        if (y < x) return ;
        if (y > maxX)
            y = maxX;
        //printf ("line %d [%d, %d] shift %d\n", lin, x, y, lazyVal);
    }
    if (x <= st && dr <= y)
    {
        if (lin == 0) update (aint[lin][nod], lazyVal + st - x);
        else update (aint[lin][nod], lazyVal - (st - x));
        return ;
    }
    int mij = (st + dr) >> 1, f1 = leftSon[lin][nod], f2 = rightSon[lin][nod];
    if (f1 == 0)
        f1 = leftSon[lin][nod] = ++cntNodes[lin],
        aint[lin][f1] = -INF;
    if (f2 == 0)
        f2 = rightSon[lin][nod] = ++cntNodes[lin],
        aint[lin][f2] = -INF;
    update (aint[lin][f1], aint[lin][nod]);
    if (lin == 0) update (aint[lin][f2], aint[lin][nod] + mij + 1 - st);
    else update (aint[lin][f2], aint[lin][nod] - (mij + 1 - 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 (nod == 0) return -INF;
    if (st == dr) return aint[lin][nod];
    int mij = (st + dr) >> 1, ans = aint[lin][nod];
    if (lin == 0) ans += pos - st;
    else ans -= (pos - st);
    if (pos <= mij) ans = max (ans, query (lin, leftSon[lin][nod], st, mij, pos));
    else ans = max (ans, query (lin, rightSon[lin][nod], mij + 1, dr, pos));
    return ans;
}

int maxDist (int x)
{
    int v1 = query (0, 1, 1, maxX, x), v2 = query (1, 1, 1, maxX, x);
    return max (v1, v2);
}

void addSegm (int x0, int x2)
{
    int mid = (x0 + x2) / 2;
    update (0, 1, 1, maxX, x0, mid, 0);
    update (1, 1, 1, maxX, mid + 1, x2, x2 - (mid + 1));
}

void delPoint (int type, int x)
{
    //printf ("del (%d, %d)\n", type, 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 ()
{
    aint[0][1] = aint[1][1] = -INF;
    cntNodes[0] = cntNodes[1] = 1;
    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;
void normalize ()
{
    for (auto &it : normT)
        it.second = ++timeCount;
    for (int i=1; i<=Q; i++)
        when[i] = normT[when[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)
    {
        //printf ("add %d to delList[%d]\n", val, nod);
        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]);
        //printf ("->size=%d\n", S[1].size ());
    }
    if (st == dr)
    {
        for (auto it : qry[st])
        {
            //printf ("solve %d (time=%d, location=%d)\n", it, when[it], location[it]);
            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);
    }
/*    for (auto it : delList[nod])
        printf ("add (%d, %d)\n", type[it], x[it]);*/
//    bool needToPrint = (setChanges[changesLine].size () > 0);
    rollBack (changesLine), changesLine --;
//    if (needToPrint) printf ("->size=%d\n", S[1].size ());
}

int main ()
{
//freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);

scanf ("%d %d %d", &N, &K, &Q), S.resize (K + 1);
for (int i=1; i<=N; i++)
    scanf ("%d %d %d %d", &x[i], &type[i], &a[i], &b[i]),
    S[type[i]].insert (x[i]), normT[a[i]] = 1, normT[b[i]] = 1;
init ();
/*printf ("%d\n", maxDist (5));
return 0;*/
for (int i=1; i<=Q; i++)
    scanf ("%d %d", &location[i], &when[i]), normT[when[i]] = 1;
normalize ();
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;
}

Compilation message

new_home.cpp: In function 'int main()':
new_home.cpp:200:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 scanf ("%d %d %d", &N, &K, &Q), S.resize (K + 1);
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
new_home.cpp:203:46: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%d %d %d %d", &x[i], &type[i], &a[i], &b[i]),
     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
     S[type[i]].insert (x[i]), normT[a[i]] = 1, normT[b[i]] = 1;
     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
new_home.cpp:208:44: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%d %d", &location[i], &when[i]), normT[when[i]] = 1;
     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	3 ms	612 KB	Output is correct
3	Correct	2 ms	612 KB	Output is correct
4	Correct	4 ms	612 KB	Output is correct
5	Correct	3 ms	616 KB	Output is correct
6	Correct	27 ms	4188 KB	Output is correct
7	Correct	8 ms	4188 KB	Output is correct
8	Correct	16 ms	4188 KB	Output is correct
9	Correct	7 ms	4188 KB	Output is correct
10	Correct	28 ms	4188 KB	Output is correct
11	Correct	17 ms	4188 KB	Output is correct
12	Correct	23 ms	4188 KB	Output is correct
13	Correct	15 ms	4188 KB	Output is correct
14	Correct	19 ms	4188 KB	Output is correct
15	Correct	14 ms	4188 KB	Output is correct
16	Correct	12 ms	4188 KB	Output is correct
17	Correct	17 ms	4188 KB	Output is correct
18	Correct	12 ms	4188 KB	Output is correct
19	Correct	11 ms	4188 KB	Output is correct
20	Correct	14 ms	4188 KB	Output is correct
21	Correct	2 ms	4188 KB	Output is correct
22	Correct	5 ms	4188 KB	Output is correct
23	Correct	9 ms	4188 KB	Output is correct
24	Correct	11 ms	4188 KB	Output is correct
25	Correct	15 ms	4188 KB	Output is correct
26	Correct	20 ms	4588 KB	Output is correct
27	Correct	4 ms	4588 KB	Output is correct
28	Correct	15 ms	4588 KB	Output is correct
29	Correct	17 ms	4588 KB	Output is correct
30	Correct	15 ms	4588 KB	Output is correct

Subtask #2
0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	3 ms	612 KB	Output is correct
3	Correct	2 ms	612 KB	Output is correct
4	Correct	4 ms	612 KB	Output is correct
5	Correct	3 ms	616 KB	Output is correct
6	Correct	27 ms	4188 KB	Output is correct
7	Correct	8 ms	4188 KB	Output is correct
8	Correct	16 ms	4188 KB	Output is correct
9	Correct	7 ms	4188 KB	Output is correct
10	Correct	28 ms	4188 KB	Output is correct
11	Correct	17 ms	4188 KB	Output is correct
12	Correct	23 ms	4188 KB	Output is correct
13	Correct	15 ms	4188 KB	Output is correct
14	Correct	19 ms	4188 KB	Output is correct
15	Correct	14 ms	4188 KB	Output is correct
16	Correct	12 ms	4188 KB	Output is correct
17	Correct	17 ms	4188 KB	Output is correct
18	Correct	12 ms	4188 KB	Output is correct
19	Correct	11 ms	4188 KB	Output is correct
20	Correct	14 ms	4188 KB	Output is correct
21	Correct	2 ms	4188 KB	Output is correct
22	Correct	5 ms	4188 KB	Output is correct
23	Correct	9 ms	4188 KB	Output is correct
24	Correct	11 ms	4188 KB	Output is correct
25	Correct	15 ms	4188 KB	Output is correct
26	Correct	20 ms	4588 KB	Output is correct
27	Correct	4 ms	4588 KB	Output is correct
28	Correct	15 ms	4588 KB	Output is correct
29	Correct	17 ms	4588 KB	Output is correct
30	Correct	15 ms	4588 KB	Output is correct
31	Execution timed out	5029 ms	287796 KB	Time limit exceeded
32	Halted	0 ms	0 KB	-

Subtask #3
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	3642 ms	1038432 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
2	Halted	0 ms	0 KB	-

Subtask #4
0 / 23.0

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

Subtask #5
0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	3 ms	612 KB	Output is correct
3	Correct	2 ms	612 KB	Output is correct
4	Correct	4 ms	612 KB	Output is correct
5	Correct	3 ms	616 KB	Output is correct
6	Correct	27 ms	4188 KB	Output is correct
7	Correct	8 ms	4188 KB	Output is correct
8	Correct	16 ms	4188 KB	Output is correct
9	Correct	7 ms	4188 KB	Output is correct
10	Correct	28 ms	4188 KB	Output is correct
11	Correct	17 ms	4188 KB	Output is correct
12	Correct	23 ms	4188 KB	Output is correct
13	Correct	15 ms	4188 KB	Output is correct
14	Correct	19 ms	4188 KB	Output is correct
15	Correct	14 ms	4188 KB	Output is correct
16	Correct	12 ms	4188 KB	Output is correct
17	Correct	17 ms	4188 KB	Output is correct
18	Correct	12 ms	4188 KB	Output is correct
19	Correct	11 ms	4188 KB	Output is correct
20	Correct	14 ms	4188 KB	Output is correct
21	Correct	2 ms	4188 KB	Output is correct
22	Correct	5 ms	4188 KB	Output is correct
23	Correct	9 ms	4188 KB	Output is correct
24	Correct	11 ms	4188 KB	Output is correct
25	Correct	15 ms	4188 KB	Output is correct
26	Correct	20 ms	4588 KB	Output is correct
27	Correct	4 ms	4588 KB	Output is correct
28	Correct	15 ms	4588 KB	Output is correct
29	Correct	17 ms	4588 KB	Output is correct
30	Correct	15 ms	4588 KB	Output is correct
31	Execution timed out	5029 ms	287796 KB	Time limit exceeded
32	Halted	0 ms	0 KB	-

Subtask #6
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	3 ms	612 KB	Output is correct
3	Correct	2 ms	612 KB	Output is correct
4	Correct	4 ms	612 KB	Output is correct
5	Correct	3 ms	616 KB	Output is correct
6	Correct	27 ms	4188 KB	Output is correct
7	Correct	8 ms	4188 KB	Output is correct
8	Correct	16 ms	4188 KB	Output is correct
9	Correct	7 ms	4188 KB	Output is correct
10	Correct	28 ms	4188 KB	Output is correct
11	Correct	17 ms	4188 KB	Output is correct
12	Correct	23 ms	4188 KB	Output is correct
13	Correct	15 ms	4188 KB	Output is correct
14	Correct	19 ms	4188 KB	Output is correct
15	Correct	14 ms	4188 KB	Output is correct
16	Correct	12 ms	4188 KB	Output is correct
17	Correct	17 ms	4188 KB	Output is correct
18	Correct	12 ms	4188 KB	Output is correct
19	Correct	11 ms	4188 KB	Output is correct
20	Correct	14 ms	4188 KB	Output is correct
21	Correct	2 ms	4188 KB	Output is correct
22	Correct	5 ms	4188 KB	Output is correct
23	Correct	9 ms	4188 KB	Output is correct
24	Correct	11 ms	4188 KB	Output is correct
25	Correct	15 ms	4188 KB	Output is correct
26	Correct	20 ms	4588 KB	Output is correct
27	Correct	4 ms	4588 KB	Output is correct
28	Correct	15 ms	4588 KB	Output is correct
29	Correct	17 ms	4588 KB	Output is correct
30	Correct	15 ms	4588 KB	Output is correct
31	Execution timed out	5029 ms	287796 KB	Time limit exceeded
32	Halted	0 ms	0 KB	-

답안 #49642

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 0 / 7.0

Subtask #3 0 / 10.0

Subtask #4 0 / 23.0

Subtask #5 0 / 35.0

Subtask #6 0 / 20.0

Subtask #1
5.0 / 5.0

Subtask #2
0 / 7.0

Subtask #3
0 / 10.0

Subtask #4
0 / 23.0

Subtask #5
0 / 35.0

Subtask #6
0 / 20.0