oj.uz

답안 #49726

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
49726 2018-06-02T10:34:04 Z SpaimaCarpatilor 새 집 (APIO18_new_home) C++17
10 / 100
 2900 ms 143988 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;
    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 (i > 1) addSegm (S[i - 1].second, +INF);
            if (i <= newN) addSegm (-INF, S[i].second);
        }
    }
    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:215: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

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

Subtask #2
0 / 7.0

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

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 615 ms 81036 KB Output is correct
2 Correct 640 ms 84276 KB Output is correct
3 Correct 567 ms 84276 KB Output is correct
4 Correct 696 ms 84276 KB Output is correct
5 Correct 771 ms 123276 KB Output is correct
6 Correct 635 ms 123276 KB Output is correct
7 Correct 510 ms 123276 KB Output is correct
8 Correct 634 ms 123276 KB Output is correct
9 Correct 654 ms 123276 KB Output is correct
10 Correct 710 ms 123276 KB Output is correct
11 Correct 388 ms 123276 KB Output is correct
12 Correct 524 ms 123276 KB Output is correct

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2412 ms 139924 KB Output is correct
2 Correct 260 ms 139924 KB Output is correct
3 Correct 2900 ms 143988 KB Output is correct
4 Incorrect 1601 ms 143988 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

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

Subtask #6
0 / 20.0

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