oj.uz

Submission #49727

# Submission time Handle Problem Language Result Execution time Memory
49727 2018-06-02T10:36:46 Z SpaimaCarpatilor New Home (APIO18_new_home) C++17
10 / 100
 3050 ms 166652 KB 
#include<bits/stdc++.h>

using namespace std;

int newN, 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];
pair < int, int > S[300009];
int prv[300009], nxt[300009];
vector < pair < int, int > > setChanges[40];

void update (int &x, int y)
{
    if (y > x)
        changes[changesLine].push_back ({&x, x}),
        x = y;
}

void rollBack (int id)
{
    reverse (changes[id].begin (), changes[id].end ());
    for (auto it : changes[id])
        *it.first = it.second;
    changes[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 maxDist (int x)
{
    int v1 = query (0, xCount - x + 1) + realX[x];
    int v2 = query (1, x) - realX[x];
    v1 = max (v1, v2);
    if (v1 >= 1e8) return -1;
    return v1;
}

void addSegm (int x0, int x2)
{
//    printf ("+[%d, %d]\n", x0, x2);
    int mid = (x0 + x2) / 2, pos;
    if (mid < realX[1]) pos = 0;
    else pos = lower_bound (realX + 1, realX + xCount + 1, mid + 1) - realX - 1;
    if (pos >= 1) update (0, xCount - pos + 1, -x0);
    if (pos < xCount) update (1, pos + 1, x2);
}

void delPoint (int it)
{
    int it0 = prv[it], it2 = nxt[it];
    int x0 = -INF, x2 = +INF;
    if (type[it0] == type[it]) x0 = x[it0];
    if (type[it2] == type[it]) x2 = x[it2];
    if (x2 > x0)
        addSegm (x0, x2);
    changes[changesLine].push_back ({&nxt[it0], nxt[it0]});
    changes[changesLine].push_back ({&prv[it2], prv[it2]});
    nxt[it0] = it2, prv[it2] = it0;
}

pair < pair < int, int >, int > normS[300009];
void init ()
{
    for (int i=1; i<=xCount; i++)
        aib[0][i] = aib[1][i] = -INF;
    for (int i=1; i<=N; i++)
        if (a[i] <= b[i])
            normS[++newN] = {{type[i], x[i]}, i};
    sort (normS + 1, normS + newN + 1);
    for (int i=1; i<=newN; i++)
        S[i] = normS[i].first;
    normS[newN + 1].second = newN + 1;
    for (int i=1; i<=newN; i++)
        prv[normS[i].second] = normS[i - 1].second,
        nxt[normS[i].second] = normS[i + 1].second;
    prv[newN + 1] = normS[newN].second, nxt[0] = normS[1].second;
    S[0].second = -INF, S[newN + 1].second = +INF;
    S[0].first = 0, S[newN + 1].first = K + 1;
    for (int i=1; i<=newN + 1; i++)
    {
        if (S[i].first == S[i - 1].first) addSegm (S[i - 1].second, S[i].second);
        else
        if (S[i].first == S[i - 1].first + 1)
        {
            if (i > 1) addSegm (S[i - 1].second, +INF);
            if (i <= newN) addSegm (-INF, S[i].second);
        }
        else
        {
            addSegm (-INF, INF);
            break;
        }
    }
    changes[changesLine].clear ();
/*    printf ("%d\n", maxDist (1));
    printf ("%d\n", maxDist (2));
    exit (0);*/
//    printf ("done initializing\n");
}

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++)
        when[i] = lower_bound (normT.begin (), normT.end (), when[i]) - normT.begin () + 1,
        location[i] = lower_bound (realX + 1, realX + xCount, location[i]) - realX;
    for (int i=1; i<=N; i++)
    {
        a[i] = lower_bound (normT.begin (), normT.end (), a[i]) - normT.begin () + 1;
        if (b[i] < normT[0]) b[i] = 0;
        else b[i] = lower_bound (normT.begin (), normT.end (), b[i] + 1) - normT.begin ();
    }
}

vector < int > delList[1200009], qry[300009];
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 ()
{
    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 (it);
    if (st == dr)
    {
        /*printf ("%d:", st);
        for (int i=nxt[0]; i<=newN; i=nxt[i])
            printf (" %d", i);
        printf ("\n");*/
        for (auto it : qry[st])
            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 --;
    //for (auto it : delList[nod])
      //  printf ("roll back\n");
}

void Read (int &x);
int main ()
{
//freopen ("100", "r", stdin);
//freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);

Read (N), Read (K), Read (Q), 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 ();
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:222: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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 35576 KB Output is correct
2 Correct 32 ms 35708 KB Output is correct
3 Correct 35 ms 35744 KB Output is correct
4 Correct 34 ms 35744 KB Output is correct
5 Correct 35 ms 35788 KB Output is correct
6 Incorrect 35 ms 35996 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 35576 KB Output is correct
2 Correct 32 ms 35708 KB Output is correct
3 Correct 35 ms 35744 KB Output is correct
4 Correct 34 ms 35744 KB Output is correct
5 Correct 35 ms 35788 KB Output is correct
6 Incorrect 35 ms 35996 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 738 ms 81100 KB Output is correct
2 Correct 683 ms 84360 KB Output is correct
3 Correct 616 ms 84360 KB Output is correct
4 Correct 719 ms 84360 KB Output is correct
5 Correct 732 ms 123144 KB Output is correct
6 Correct 639 ms 123144 KB Output is correct
7 Correct 551 ms 123144 KB Output is correct
8 Correct 610 ms 123144 KB Output is correct
9 Correct 607 ms 123144 KB Output is correct
10 Correct 616 ms 123144 KB Output is correct
11 Correct 430 ms 123144 KB Output is correct
12 Correct 507 ms 123144 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3050 ms 139804 KB Output is correct
2 Correct 244 ms 139804 KB Output is correct
3 Correct 2513 ms 143732 KB Output is correct
4 Correct 1319 ms 143732 KB Output is correct
5 Correct 1860 ms 143732 KB Output is correct
6 Correct 1787 ms 143732 KB Output is correct
7 Correct 2346 ms 166652 KB Output is correct
8 Incorrect 2435 ms 166652 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 35576 KB Output is correct
2 Correct 32 ms 35708 KB Output is correct
3 Correct 35 ms 35744 KB Output is correct
4 Correct 34 ms 35744 KB Output is correct
5 Correct 35 ms 35788 KB Output is correct
6 Incorrect 35 ms 35996 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 35576 KB Output is correct
2 Correct 32 ms 35708 KB Output is correct
3 Correct 35 ms 35744 KB Output is correct
4 Correct 34 ms 35744 KB Output is correct
5 Correct 35 ms 35788 KB Output is correct
6 Incorrect 35 ms 35996 KB Output isn't correct
7 Halted 0 ms 0 KB -