제출 #659293

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
659293		Jeff12345121	전차 (CEOI13_tram)	C++14	0 / 100	191 ms	1100 KiB

tram

#include <bits/stdc++.h>
#define REP(i, n) for (int i = 1; i <= (n); i++)
#define int long long
using namespace std;

#ifdef LOCAL
ifstream in("in.in");
ofstream out("out.out");
#else
#define in cin
#define out cout
#endif

/// brute

int n, m;
const int nmax = 150005, inf = (1LL << 60);
pair<int, int> queries[nmax];
int a[nmax][3];
set<pair<int, int>> s;
set<int> dis_s[2];

int squared(int x)
{
    return x * x;
}
int find_distance(int y, int x, int i, int j)
{
    return squared(y - i) + squared(x - j);
}
int get_dis(int y, int x)
{
    int val[3] = {inf, inf, inf}; /// min dis from some other value
    for (int k = 1; k <= 2; k++)
    {
        auto after = dis_s[k - 1].lower_bound(y);
        auto before = after;
        if (before != dis_s[k - 1].begin())
        {
            before--;
            val[k] = min(val[k], find_distance(k, *before, x, y));
        }
        if (after != dis_s[k - 1].end())
        {
            val[k] = min(val[k], find_distance(k, *after, x, y));
        }
    }
    return min(val[1], val[2]);
}

pair<int, int> sol;
int max_dis = -inf;

void check(int i, int j)
{
    if ((1 <= i && i <= n && 1 <= j && j <= 2) && a[i][j] == 0)
    {
        int dis = get_dis(i, j);
        if (dis > max_dis)
        {
            max_dis = dis;
            sol = {i, j};
        }
        else if (dis == max_dis && (pair<int, int>{i, j}) < sol)
        {
            sol = {i, j};
        }
    }
};

void handle(int y1, int y2)
{
    for (int j = 1; j <= 2; j++)
    {
        check(y1, j);
        check(y2, j);
    }
    /// now check the inbetween spot.
    vector<int> mids;
    mids.push_back((y1 + y2) / 2);
    if ((y1 + y2) % 2 == 1)
    {
        mids.push_back((y1 + 2) / 2 + 1);
    }
    for (auto k : mids)
    {
        for (int j = 1; j <= 2; j++)
        {
            check(k, j);
            check(k - 1, j);
            check(k + 1, j);
        }
    }
};
void recalculate(set<pair<int, int>>::iterator it)
{
    auto nxt = it;
    nxt++;

    if (nxt != s.end())
    {
        handle(it->first, nxt->first);
    }
    else
    {
        handle(it->first, n);
    }
}

typedef pair<int, pair<int, int>> cool_val;

cool_val cool_max(cool_val a, cool_val b)
{
    if (a.first != b.first)
    {
        return max(a, b);
    }
    else
    {
        return min(a, b);
    }
}

struct cmp
{
    bool operator()(pair<int, cool_val> a, pair<int, cool_val> b)
    {
        if (a.second.first != b.second.first)
        {
            return a.second.first < b.second.first;
        }
        if (a.second.second != b.second.second)
        {
            return a.second.second > b.second.second;
        }
        return a.first < b.first;
    }
};

set<pair<int, cool_val>, cmp> solutions;

cool_val find_value(set<pair<int, int>>::iterator it)
{
    max_dis = -inf;
    recalculate(it);
    return {max_dis, sol};
}

map<int, cool_val> solutions_map;

pair<int, int> add()
{

    if (s.empty())
    {
        return {1, 1};
    }

    auto p = solutions.end();
    p--;

    cool_val final_val = p->second;

    max_dis = -inf;
    handle(1, s.begin()->first);
    cool_val first_val = {max_dis, sol};

    final_val = cool_max(final_val, first_val);
    return final_val.second;
}

pair<int, int> i_to_pair(int i)
{
    int s = 0;
    return {i, a[i][1] + 2 * a[i][2]};
}

void recalc_it(set<pair<int, int>>::iterator it)
{
    if (solutions_map.find(it->first) != solutions_map.end())
    {
        pair<int, cool_val> val = {it->first, solutions_map[it->first]};
        solutions.erase(val);
    }

    cool_val v = find_value(it);
    solutions_map[it->first] = v;
    solutions.insert({it->first, v});
}

void total_recalc(set<pair<int,int>>::iterator it)
{
    auto cl_it = it;
    if (cl_it != s.end()) {
        recalc_it(it);
    }
    if (it != s.begin()) {
        it--;
        recalc_it(it);
    }
    if (it != s.begin()) {
        it--;
        recalc_it(it);
    }
    if (it != s.begin()) {
        it--;
        recalc_it(it);
    }

    if (cl_it != s.end()) {
        cl_it++;
        if (cl_it != s.end()) {
            recalc_it(cl_it);
        }

        cl_it++;
        if (cl_it != s.end()) {
            recalc_it(cl_it);
        }

        cl_it++;
        if (cl_it != s.end()) {
            recalc_it(cl_it);
        }
    }
    
}
int32_t main()
{
    in >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        char type;
        in >> type;
        if (type == 'E')
        {
            pair<int, int> pos = add();
            auto nr = s.erase(i_to_pair(pos.first));
            if (nr > 0)
            {
                solutions.erase({pos.first, solutions_map[pos.first]});
            }

            out << pos.first << " " << pos.second << "\n";
            a[pos.first][pos.second] = 1;

            dis_s[pos.second - 1].insert(pos.first);

            auto p = s.insert(i_to_pair(pos.first)).first;

            total_recalc(p);
            /*
            recalc_it(p);
            if (p != s.begin()) {
                p--;
                recalc_it(p);
                p++;
            }
              */
            queries[i] = pos;
        }
        else
        {
            int pos;
            in >> pos;
            int y = queries[pos].first, x = queries[pos].second;
            auto nr = s.erase(i_to_pair(y));

            if (nr > 0)
            {
                solutions.erase({y, solutions_map[y]});
            }

            dis_s[queries[pos].second - 1].erase(queries[pos].first);

            a[y][x] = 0;
            if (a[y][1] == 1 || a[y][2] == 1)
            {
                auto p = s.insert(i_to_pair(y)).first;

                total_recalc(p);
            }
            else
            {
                auto p = s.lower_bound(i_to_pair(y));
                total_recalc(p);
            }
        }
    }
}

컴파일 시 표준 에러 (stderr) 메시지

tram.cpp: In function 'std::pair<long long int, long long int> i_to_pair(long long int)':
tram.cpp:174:9: warning: unused variable 's' [-Wunused-variable]
  174 |     int s = 0;
      |         ^

• Subtask 1: 0 / 10
• Subtask 2: 0 / 15
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 15
• Subtask 8: 0 / 20