oj.uz

Submission #53092

# Submission time Handle Problem Language Result Execution time Memory
53092 2018-06-28T10:35:02 Z Costin Andrei Oncescu(#1297) Tram (CEOI13_tram) C++11
100 / 100
 44 ms 4460 KB 
#include<bits/stdc++.h>

using namespace std;

int N, M, K;
bool ap[150009][3];
pair < int, int > cell[30009];
set < int > S;
set < pair < long long, pair < int, int > > > PQ;

long long getDist (int x, int y, int c)
{
    long long d = 1LL * N * N + 3;
    if (ap[c][1]) d = min (d, 1LL * (x - c) * (x - c) + (y - 1));
    if (ap[c][2]) d = min (d, 1LL * (x - c) * (x - c) + (2 - y));
    return d;
}

pair < long long, pair < int, int > > getCell (int i, int j)
{
    if (i == 0 && j == N + 1) return {-1LL * N * N - 3, {1, 1}};
    if (i == 0)
    {
        if (j == 1) return {0, {1, 1}};
        int x = 1, y = 1;
        if (ap[j][2] == 0 && ap[j][1] == 1) y = 2;
        return {-getDist (x, y, j), {x, y}};
    }
    if (j == N + 1)
    {
        if (i == N)
        {
            if (ap[N][1] && ap[N][2]) return {0, {1, 1}};
            if (ap[N][1]) return {-1, {N, 2}};
            return {-1, {N, 1}};
        }
        int x = N, y = 1;
        if (ap[i][2] == 0 && ap[i][1] == 1) y = 2;
        return {-getDist (x, y, i), {x, y}};
    }
    int mij = (i + j) >> 1;
    long long maxi = 0;
    pair < int, int > ans = {1, 1};
    if (mij > i) mij --;
    for (int k=mij; k<=mij + 2 && k<j; k++)
        for (int p=1; p<=2; p++)
        if (ap[k][p] == 0)
        {
            long long d = min (getDist (k, p, i), getDist (k, p, j));
            if (d > maxi)
                maxi = d, ans = {k, p};
        }
    return {-maxi, ans};
}

void add (int x, int y)
{
    auto it = S.lower_bound (x);
    if (*it != x)
    {
        auto it2 = it, it1 = it2; it1 --;
        auto curr = getCell (*it1, *it2);
        if (curr.first != 0) PQ.erase (curr);
        ap[x][y] = 1;
        curr = getCell (*it1, x);
        if (curr.first != 0) PQ.insert (curr);
        curr = getCell (x, *it2);
        if (curr.first != 0) PQ.insert (curr);
        S.insert (x);
        return ;
    }
    auto it2 = it, it1 = it;
    it1 --, it2 ++;
    auto curr = getCell (*it1, x);
    if (curr.first != 0) PQ.erase (curr);
    curr = getCell (x, *it2);
    if (curr.first != 0) PQ.erase (curr);
    ap[x][y] = 1;
    curr = getCell (*it1, x);
    if (curr.first != 0) PQ.insert (curr);
    curr = getCell (x, *it2);
    if (curr.first != 0) PQ.insert (curr);
}

void del (int x, int y)
{
    auto it = S.find (x);
    auto it1 = it, it2 = it;
    it1 --, it2 ++;
    auto curr = getCell (*it1, x);
    if (curr.first != 0) PQ.erase (curr);
    curr = getCell (x, *it2);
    if (curr.first != 0) PQ.erase (curr);
    if (ap[x][1] + ap[x][2] == 1)
    {
        ap[x][y] = 0;
        curr = getCell (*it1, *it2);
        if (curr.first != 0) PQ.insert (curr);
        S.erase (it);
        return ;
    }
    ap[x][y] = 0;
    curr = getCell (*it1, x);
    if (curr.first != 0) PQ.insert (curr);
    curr = getCell (x, *it2);
    if (curr.first != 0) PQ.insert (curr);
}

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

scanf ("%d %d", &N, &M);
S.insert (0), S.insert (N + 1);
PQ.insert (getCell (0, N + 1));
while (M --)
{
    char type;
    scanf ("\n%c", &type);
    K ++;
    if (type == 'E')
    {
        auto curr = *PQ.begin ();
        cell[K] = curr.second;
        printf ("%d %d\n", cell[K].first, cell[K].second);
        add (cell[K].first, cell[K].second);
/*        printf ("After ins: ");
        for (auto it : PQ)
            printf ("[(%d %d) %lld] ", it.second.first, it.second.second, -it.first);
        printf ("\n");*/
        continue;
    }
    int pos = 0;
    scanf ("%d", &pos);
    del (cell[pos].first, cell[pos].second);
/*    printf ("After del: ");
    for (auto it : PQ)
        printf ("[(%d %d) %lld] ", it.second.first, it.second.second, -it.first);
    printf ("\n");*/
}

return 0;
}

Compilation message

tram.cpp: In function 'int main()':
tram.cpp:114:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  114 | scanf ("%d %d", &N, &M);
      | ~~~~~~^~~~~~~~~~~~~~~~~
tram.cpp:120:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  120 |     scanf ("\n%c", &type);
      |     ~~~~~~^~~~~~~~~~~~~~~
tram.cpp:135:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  135 |     scanf ("%d", &pos);
      |     ~~~~~~^~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 492 KB Output is correct
2 Correct 2 ms 364 KB Output is correct
3 Correct 2 ms 364 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 492 KB Output is correct
2 Correct 3 ms 364 KB Output is correct
3 Correct 3 ms 364 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1004 KB Output is correct
2 Correct 2 ms 364 KB Output is correct
3 Correct 3 ms 876 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1004 KB Output is correct
2 Correct 2 ms 364 KB Output is correct
3 Correct 2 ms 876 KB Output is correct

Subtask #7
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 2028 KB Output is correct
2 Correct 33 ms 748 KB Output is correct
3 Correct 33 ms 1644 KB Output is correct

Subtask #8
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 4460 KB Output is correct
2 Correct 23 ms 748 KB Output is correct
3 Correct 33 ms 2028 KB Output is correct