답안 #49644 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
49644	2018-06-01T14:15:12 Z	SpaimaCarpatilor	새 집 (APIO18_new_home)	C++17	10 / 100	5000 ms	808712 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 ();
for (int i=1; i<=Q; i++)
{
    int curr = maxDist (location[i]);
    if (curr > 2e8)
        curr = -1;
    printf ("%d\n", curr);
}
return 0;
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
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	504 KB	Output is correct
2	Incorrect	2 ms	588 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #2
0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	504 KB	Output is correct
2	Incorrect	2 ms	588 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4983 ms	704784 KB	Output is correct
2	Correct	3924 ms	723552 KB	Output is correct
3	Correct	2963 ms	723552 KB	Output is correct
4	Correct	4274 ms	723552 KB	Output is correct
5	Correct	2624 ms	723552 KB	Output is correct
6	Correct	3459 ms	723552 KB	Output is correct
7	Correct	3560 ms	723552 KB	Output is correct
8	Correct	4194 ms	723552 KB	Output is correct
9	Correct	4668 ms	785072 KB	Output is correct
10	Correct	4515 ms	791840 KB	Output is correct
11	Correct	2464 ms	801132 KB	Output is correct
12	Correct	2885 ms	801132 KB	Output is correct