oj.uz

답안 #49647

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
49647 2018-06-01T15:05:39 Z SpaimaCarpatilor 새 집 (APIO18_new_home) C++17
5 / 100
 5000 ms 405608 KB 
#include<bits/stdc++.h>

using namespace std;

int N, K, Q, timeCount, xCount, x[300009], type[300009], a[300009], b[300009], location[300009], when[300009], ans[300009], realX[600009];
const int INF = 5e8;
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 = 2400009;
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 (x <= st && dr <= y)
    {
        if (lin == 0) update (aint[lin][nod], lazyVal + realX[st] - realX[x]);
        else update (aint[lin][nod], lazyVal - (realX[st] - realX[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] + realX[mij + 1] - realX[st]);
    else update (aint[lin][f2], aint[lin][nod] - (realX[mij + 1] - realX[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 += realX[pos] - realX[st];
    else ans -= (realX[pos] - realX[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, xCount, x), v2 = query (1, 1, 1, xCount, x);
    return max (v1, v2);
}

int firstBigger (int val)
{
    int p = 1, u = xCount, mij, ras = xCount + 1;
    while (p <= u)
    {
        mij = (p + u) >> 1;
        if (realX[mij] > val) ras = mij, u = mij - 1;
        else p = mij + 1;
    }
    return ras;
}

int lastSmaller (int val)
{
    int p = 1, u = xCount, mij, ras = 0;
    while (p <= u)
    {
        mij = (p + u) >> 1;
        if (realX[mij] < val) ras = mij, p = mij + 1;
        else u = mij - 1;
    }
    return ras;
}

void addLine (int type, int bg, int nd)
{
    int x = firstBigger (bg - 1), y = lastSmaller (nd + 1);
    if (x <= y)
    {
        if (type == 0) update (0, 1, 1, xCount, x, y, realX[x] - bg);
        else update (1, 1, 1, xCount, x, y, nd - realX[x]);
    }
}

void addSegm (int x0, int x2)
{
    int mid = (x0 + x2) / 2;
    addLine (0, x0, mid);
    addLine (1, mid + 1, x2);
}

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, mpX;
void normalize ()
{
    for (auto &it : normT)
        it.second = ++timeCount;
    for (auto &it : mpX)
        it.second = ++xCount, realX[xCount] = it.first;
    for (int i=1; i<=Q; i++)
        when[i] = normT[when[i]], location[i] = mpX[location[i]];
    for (int i=1; i<=N; i++)
        a[i] = normT[a[i]], b[i] = normT[b[i]], x[i] = mpX[x[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], realX[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 ());
}

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

Read (N), Read (K), Read (Q), S.resize (K + 1);
for (int i=1; i<=N; i++)
    Read (x[i]), Read (type[i]), Read (a[i]), Read (b[i]),
    normT[a[i]] = 1, normT[b[i]] = 1, mpX[x[i]] = 1, S[type[i]].insert (x[i]);
for (int i=1; i<=Q; i++)
    Read (location[i]), Read (when[i]), normT[when[i]] = 1, mpX[location[i]] = 1;
normalize ();
init ();
/*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;
}

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:257: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
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 3 ms 564 KB Output is correct
4 Correct 2 ms 616 KB Output is correct
5 Correct 3 ms 760 KB Output is correct
6 Correct 9 ms 1280 KB Output is correct
7 Correct 7 ms 1280 KB Output is correct
8 Correct 6 ms 1280 KB Output is correct
9 Correct 6 ms 1280 KB Output is correct
10 Correct 8 ms 1280 KB Output is correct
11 Correct 7 ms 1280 KB Output is correct
12 Correct 8 ms 1280 KB Output is correct
13 Correct 7 ms 1280 KB Output is correct
14 Correct 9 ms 1280 KB Output is correct
15 Correct 7 ms 1280 KB Output is correct
16 Correct 6 ms 1280 KB Output is correct
17 Correct 7 ms 1280 KB Output is correct
18 Correct 7 ms 1280 KB Output is correct
19 Correct 7 ms 1280 KB Output is correct
20 Correct 7 ms 1280 KB Output is correct
21 Correct 2 ms 1280 KB Output is correct
22 Correct 4 ms 1280 KB Output is correct
23 Correct 5 ms 1280 KB Output is correct
24 Correct 7 ms 1280 KB Output is correct
25 Correct 8 ms 1280 KB Output is correct
26 Correct 12 ms 1280 KB Output is correct
27 Correct 5 ms 1280 KB Output is correct
28 Correct 7 ms 1280 KB Output is correct
29 Correct 7 ms 1280 KB Output is correct
30 Correct 7 ms 1280 KB Output is correct

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 3 ms 564 KB Output is correct
4 Correct 2 ms 616 KB Output is correct
5 Correct 3 ms 760 KB Output is correct
6 Correct 9 ms 1280 KB Output is correct
7 Correct 7 ms 1280 KB Output is correct
8 Correct 6 ms 1280 KB Output is correct
9 Correct 6 ms 1280 KB Output is correct
10 Correct 8 ms 1280 KB Output is correct
11 Correct 7 ms 1280 KB Output is correct
12 Correct 8 ms 1280 KB Output is correct
13 Correct 7 ms 1280 KB Output is correct
14 Correct 9 ms 1280 KB Output is correct
15 Correct 7 ms 1280 KB Output is correct
16 Correct 6 ms 1280 KB Output is correct
17 Correct 7 ms 1280 KB Output is correct
18 Correct 7 ms 1280 KB Output is correct
19 Correct 7 ms 1280 KB Output is correct
20 Correct 7 ms 1280 KB Output is correct
21 Correct 2 ms 1280 KB Output is correct
22 Correct 4 ms 1280 KB Output is correct
23 Correct 5 ms 1280 KB Output is correct
24 Correct 7 ms 1280 KB Output is correct
25 Correct 8 ms 1280 KB Output is correct
26 Correct 12 ms 1280 KB Output is correct
27 Correct 5 ms 1280 KB Output is correct
28 Correct 7 ms 1280 KB Output is correct
29 Correct 7 ms 1280 KB Output is correct
30 Correct 7 ms 1280 KB Output is correct
31 Execution timed out 5016 ms 92964 KB Time limit exceeded
32 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 4042 ms 405608 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 Execution timed out 5046 ms 405608 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 3 ms 564 KB Output is correct
4 Correct 2 ms 616 KB Output is correct
5 Correct 3 ms 760 KB Output is correct
6 Correct 9 ms 1280 KB Output is correct
7 Correct 7 ms 1280 KB Output is correct
8 Correct 6 ms 1280 KB Output is correct
9 Correct 6 ms 1280 KB Output is correct
10 Correct 8 ms 1280 KB Output is correct
11 Correct 7 ms 1280 KB Output is correct
12 Correct 8 ms 1280 KB Output is correct
13 Correct 7 ms 1280 KB Output is correct
14 Correct 9 ms 1280 KB Output is correct
15 Correct 7 ms 1280 KB Output is correct
16 Correct 6 ms 1280 KB Output is correct
17 Correct 7 ms 1280 KB Output is correct
18 Correct 7 ms 1280 KB Output is correct
19 Correct 7 ms 1280 KB Output is correct
20 Correct 7 ms 1280 KB Output is correct
21 Correct 2 ms 1280 KB Output is correct
22 Correct 4 ms 1280 KB Output is correct
23 Correct 5 ms 1280 KB Output is correct
24 Correct 7 ms 1280 KB Output is correct
25 Correct 8 ms 1280 KB Output is correct
26 Correct 12 ms 1280 KB Output is correct
27 Correct 5 ms 1280 KB Output is correct
28 Correct 7 ms 1280 KB Output is correct
29 Correct 7 ms 1280 KB Output is correct
30 Correct 7 ms 1280 KB Output is correct
31 Execution timed out 5016 ms 92964 KB Time limit exceeded
32 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 3 ms 564 KB Output is correct
4 Correct 2 ms 616 KB Output is correct
5 Correct 3 ms 760 KB Output is correct
6 Correct 9 ms 1280 KB Output is correct
7 Correct 7 ms 1280 KB Output is correct
8 Correct 6 ms 1280 KB Output is correct
9 Correct 6 ms 1280 KB Output is correct
10 Correct 8 ms 1280 KB Output is correct
11 Correct 7 ms 1280 KB Output is correct
12 Correct 8 ms 1280 KB Output is correct
13 Correct 7 ms 1280 KB Output is correct
14 Correct 9 ms 1280 KB Output is correct
15 Correct 7 ms 1280 KB Output is correct
16 Correct 6 ms 1280 KB Output is correct
17 Correct 7 ms 1280 KB Output is correct
18 Correct 7 ms 1280 KB Output is correct
19 Correct 7 ms 1280 KB Output is correct
20 Correct 7 ms 1280 KB Output is correct
21 Correct 2 ms 1280 KB Output is correct
22 Correct 4 ms 1280 KB Output is correct
23 Correct 5 ms 1280 KB Output is correct
24 Correct 7 ms 1280 KB Output is correct
25 Correct 8 ms 1280 KB Output is correct
26 Correct 12 ms 1280 KB Output is correct
27 Correct 5 ms 1280 KB Output is correct
28 Correct 7 ms 1280 KB Output is correct
29 Correct 7 ms 1280 KB Output is correct
30 Correct 7 ms 1280 KB Output is correct
31 Execution timed out 5016 ms 92964 KB Time limit exceeded
32 Halted 0 ms 0 KB -