Submission #49644

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
49644	2018-06-01T14:15:12 Z	SpaimaCarpatilor	New Home (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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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