답안 #49641 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
49641	2018-06-01T14:11:09 Z	SpaimaCarpatilor	새 집 (APIO18_new_home)	C++17	5 / 100	1310 ms	347252 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 ();
}

int cntNodes[2], aint[2][2000009], leftSon[2][2000009], rightSon[2][2000009];
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:199: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:202: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:207: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	380 KB	Output is correct
2	Correct	2 ms	616 KB	Output is correct
3	Correct	2 ms	616 KB	Output is correct
4	Correct	2 ms	616 KB	Output is correct
5	Correct	4 ms	616 KB	Output is correct
6	Correct	22 ms	4088 KB	Output is correct
7	Correct	5 ms	4088 KB	Output is correct
8	Correct	12 ms	4088 KB	Output is correct
9	Correct	5 ms	4088 KB	Output is correct
10	Correct	23 ms	4088 KB	Output is correct
11	Correct	20 ms	4088 KB	Output is correct
12	Correct	26 ms	4224 KB	Output is correct
13	Correct	16 ms	4224 KB	Output is correct
14	Correct	18 ms	4224 KB	Output is correct
15	Correct	14 ms	4224 KB	Output is correct
16	Correct	16 ms	4224 KB	Output is correct
17	Correct	16 ms	4224 KB	Output is correct
18	Correct	15 ms	4224 KB	Output is correct
19	Correct	12 ms	4224 KB	Output is correct
20	Correct	23 ms	4224 KB	Output is correct
21	Correct	4 ms	4224 KB	Output is correct
22	Correct	9 ms	4224 KB	Output is correct
23	Correct	13 ms	4224 KB	Output is correct
24	Correct	12 ms	4224 KB	Output is correct
25	Correct	18 ms	4224 KB	Output is correct
26	Correct	22 ms	4588 KB	Output is correct
27	Correct	5 ms	4588 KB	Output is correct
28	Correct	17 ms	4588 KB	Output is correct
29	Correct	17 ms	4588 KB	Output is correct
30	Correct	14 ms	4588 KB	Output is correct

Subtask #2
0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	380 KB	Output is correct
2	Correct	2 ms	616 KB	Output is correct
3	Correct	2 ms	616 KB	Output is correct
4	Correct	2 ms	616 KB	Output is correct
5	Correct	4 ms	616 KB	Output is correct
6	Correct	22 ms	4088 KB	Output is correct
7	Correct	5 ms	4088 KB	Output is correct
8	Correct	12 ms	4088 KB	Output is correct
9	Correct	5 ms	4088 KB	Output is correct
10	Correct	23 ms	4088 KB	Output is correct
11	Correct	20 ms	4088 KB	Output is correct
12	Correct	26 ms	4224 KB	Output is correct
13	Correct	16 ms	4224 KB	Output is correct
14	Correct	18 ms	4224 KB	Output is correct
15	Correct	14 ms	4224 KB	Output is correct
16	Correct	16 ms	4224 KB	Output is correct
17	Correct	16 ms	4224 KB	Output is correct
18	Correct	15 ms	4224 KB	Output is correct
19	Correct	12 ms	4224 KB	Output is correct
20	Correct	23 ms	4224 KB	Output is correct
21	Correct	4 ms	4224 KB	Output is correct
22	Correct	9 ms	4224 KB	Output is correct
23	Correct	13 ms	4224 KB	Output is correct
24	Correct	12 ms	4224 KB	Output is correct
25	Correct	18 ms	4224 KB	Output is correct
26	Correct	22 ms	4588 KB	Output is correct
27	Correct	5 ms	4588 KB	Output is correct
28	Correct	17 ms	4588 KB	Output is correct
29	Correct	17 ms	4588 KB	Output is correct
30	Correct	14 ms	4588 KB	Output is correct
31	Runtime error	781 ms	257036 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
32	Halted	0 ms	0 KB	-

Subtask #3
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	936 ms	326000 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	Runtime error	1310 ms	347252 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
2	Halted	0 ms	0 KB	-

Subtask #5
0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	380 KB	Output is correct
2	Correct	2 ms	616 KB	Output is correct
3	Correct	2 ms	616 KB	Output is correct
4	Correct	2 ms	616 KB	Output is correct
5	Correct	4 ms	616 KB	Output is correct
6	Correct	22 ms	4088 KB	Output is correct
7	Correct	5 ms	4088 KB	Output is correct
8	Correct	12 ms	4088 KB	Output is correct
9	Correct	5 ms	4088 KB	Output is correct
10	Correct	23 ms	4088 KB	Output is correct
11	Correct	20 ms	4088 KB	Output is correct
12	Correct	26 ms	4224 KB	Output is correct
13	Correct	16 ms	4224 KB	Output is correct
14	Correct	18 ms	4224 KB	Output is correct
15	Correct	14 ms	4224 KB	Output is correct
16	Correct	16 ms	4224 KB	Output is correct
17	Correct	16 ms	4224 KB	Output is correct
18	Correct	15 ms	4224 KB	Output is correct
19	Correct	12 ms	4224 KB	Output is correct
20	Correct	23 ms	4224 KB	Output is correct
21	Correct	4 ms	4224 KB	Output is correct
22	Correct	9 ms	4224 KB	Output is correct
23	Correct	13 ms	4224 KB	Output is correct
24	Correct	12 ms	4224 KB	Output is correct
25	Correct	18 ms	4224 KB	Output is correct
26	Correct	22 ms	4588 KB	Output is correct
27	Correct	5 ms	4588 KB	Output is correct
28	Correct	17 ms	4588 KB	Output is correct
29	Correct	17 ms	4588 KB	Output is correct
30	Correct	14 ms	4588 KB	Output is correct
31	Runtime error	781 ms	257036 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
32	Halted	0 ms	0 KB	-

Subtask #6
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	380 KB	Output is correct
2	Correct	2 ms	616 KB	Output is correct
3	Correct	2 ms	616 KB	Output is correct
4	Correct	2 ms	616 KB	Output is correct
5	Correct	4 ms	616 KB	Output is correct
6	Correct	22 ms	4088 KB	Output is correct
7	Correct	5 ms	4088 KB	Output is correct
8	Correct	12 ms	4088 KB	Output is correct
9	Correct	5 ms	4088 KB	Output is correct
10	Correct	23 ms	4088 KB	Output is correct
11	Correct	20 ms	4088 KB	Output is correct
12	Correct	26 ms	4224 KB	Output is correct
13	Correct	16 ms	4224 KB	Output is correct
14	Correct	18 ms	4224 KB	Output is correct
15	Correct	14 ms	4224 KB	Output is correct
16	Correct	16 ms	4224 KB	Output is correct
17	Correct	16 ms	4224 KB	Output is correct
18	Correct	15 ms	4224 KB	Output is correct
19	Correct	12 ms	4224 KB	Output is correct
20	Correct	23 ms	4224 KB	Output is correct
21	Correct	4 ms	4224 KB	Output is correct
22	Correct	9 ms	4224 KB	Output is correct
23	Correct	13 ms	4224 KB	Output is correct
24	Correct	12 ms	4224 KB	Output is correct
25	Correct	18 ms	4224 KB	Output is correct
26	Correct	22 ms	4588 KB	Output is correct
27	Correct	5 ms	4588 KB	Output is correct
28	Correct	17 ms	4588 KB	Output is correct
29	Correct	17 ms	4588 KB	Output is correct
30	Correct	14 ms	4588 KB	Output is correct
31	Runtime error	781 ms	257036 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
32	Halted	0 ms	0 KB	-

답안 #49641

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