Submission #770201

#	Time	Username	Problem	Language	Result	Execution time	Memory
770201		danikoynov	Walk (CEOI06_walk)	C++14	0 / 100	193 ms	39116 KiB

walk

#include <bits/stdc++.h>
#define endl "\n"

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const int maxn = 1e5 + 10, maxc = 1000; /// fix this

struct point
{
    int x, y;

    void read()
    {
        cin >> x >> y;
    }

    point(int _x = 0, int _y = 0)
    {
        x = _x;
        y = _y;
    }
};

struct rectangle
{
    point A, B;

    void read()
    {
        A.read();
        B.read();
    }
} r[maxn];

struct line
{
    int x,  en;
    int type;
    int idx;
    line(int _x, int _type, int _idx)
    {
        type = _type;
        x = _x;
        idx = _idx;
    }

    bool operator < (const line &l) const
    {
        if (x == l.x)
            return type > l.type;
        return x < l.x;
    }
};

int st_x, st_y, n;
vector < pair < int, int > > adj[maxn * 2];
void read()
{
    cin >> st_x >> st_y >> n;
    for (int i = 1; i <= n; i ++)
    {
        r[i].A.read();
        r[i].B.read();
        if (r[i].A.x > r[i].B.x)
            swap(r[i].A.x, r[i].B.x);
        if (r[i].A.y > r[i].B.y)
            swap(r[i].A.y, r[i].B.y);

        r[i].A.y += maxc;
        r[i].B.y += maxc;
    }
    st_y += maxc;
}

stack < int > tree[8 * maxc];
int sum[8 * maxc];
int get_index(int root, int left, int right, int qleft, int qright)
{
    if (sum[root] == 0)
        return -1;

    if (left > qright || right < qleft)
    return -1;

    if (left == right)
        return left;

        int mid = (left + right) / 2;
    if (left >= qleft && right <= qright)
    {
        if (sum[root * 2] > 0)
            return get_index(root * 2, left, mid, qleft, qright);
        return get_index(root * 2 + 1, mid + 1, right, qleft, qright);
    }

  ///  int mid = (left + right) / 2;
    return max(get_index(root * 2, left, mid, qleft, qright),
               get_index(root * 2 + 1, mid + 1, right, qleft, qright));
}

int update(int root, int left, int right, int pos, int val)
{
    if (left == right)
    {
        int to = 0;
        if (val == -1)
        {

            to = tree[root].top();
            tree[root].pop(), sum[root] --;
        }
        else
        {
            to = -1;
            tree[root].push(val), sum[root] ++;
        }
        return to;
    }

    int mid = (left + right) / 2, ans;
    if (pos <= mid)
        ans = update(root * 2, left, mid, pos, val);
    else
        ans =update(root * 2 + 1, mid + 1, right, pos, val);

    sum[root] = sum[root * 2] + sum[root * 2 + 1];
    return ans;
}

int distance_to_end(int idx)
{
    if (idx == 0)
    {
        return st_x;
    }
    if (idx <= n)
    {
        int x = r[idx].B.x, y = r[idx].A.y - 1;
        ///cout << x << " : " << y << " : " << st_x << " : " << st_y << endl;
        return abs(x - st_x) + abs(y - st_y);
    }
    if (idx > n)
    {
        idx -= n;
        int x = r[idx].B.x, y =r[idx].B.y + 1;
        return abs(x - st_x) + abs(y - st_y);
    }
}

pair < int, int > get_point(int v)
{
    if (v == 0)
    return {0, maxc};

    if (v <= n)
    {
        return {r[v].B.x, r[v].A.y - 1};
    }

    if (v > n)
    {
        v -= n;
        return {r[v].B.x, r[v].B.y + 1};
    }
}

int get_distance(int v, int u)
{
    pair < int, int > s = get_point(v);
    pair < int, int > t = get_point(u);

    return abs(s.first - t.first) + abs(s.second - t.second);
}

int used[2 * maxn], dp[2 * maxn];
int dfs(int v)
{
    used[v] = 1;
    for (pair < int, int > nb : adj[v])
    {
        int u = nb.first;
        if (!used[u])
            dfs(u);
        dp[v] = min(dp[v], dp[u] + nb.second);
    }
}
void sweep_line()
{
    vector < line > event;
    for (int i = 1; i <= n; i ++)
    {
        event.push_back(line(r[i].A.x, 1, i));
    }
    event.push_back(line(st_x, 2, -1));

    sort(event.begin(), event.end());
    for (int i = 0; i <= 2 * n; i ++)
        dp[i] = 1e9;
    int lb = 0, rb = 2 * maxc - 1;
    update(1, lb, rb, maxc, 0);
    for (int i = 0; i < event.size(); i ++)
    {
        line cur = event[i];
        int idx = cur.idx;

        if (cur.type == 2)
            {
                while(true)
                {
                    int pos = get_index(1, lb, rb, lb, rb);
                    if (pos == -1)
                        break;
                    int ver = update(1, lb, rb, pos, -1);
                    dp[ver] = distance_to_end(ver);
                    ///cout << "dp " << dp[ver] << " " << ver << endl;
                    ///adj[ver].push_back(idx);
                    ///adj[ver].push_back(idx + n);
                }
                return;
            }

        while(true)
        {
                    int pos = get_index(1, lb, rb, r[idx].A.y, r[idx].B.y);
                    if (pos == -1)
                        break;
                    int ver = update(1, lb, rb, pos, -1);
                    //cout << ver << " : " << idx << endl;
                    //cout << ver << " : " << idx + n << endl;
                adj[ver].push_back({idx, get_distance(ver, idx)});
                adj[ver].push_back({idx + n, get_distance(ver, idx + n)});
                //cout << adj[ver].back().second << endl;
        }
        update(1, lb, rb, r[idx].A.y - 1, idx);
        update(1, lb, rb, r[idx].B.y + 1, idx + n);
    }
}

void solve()
{
    read();
    sweep_line();

    dfs(0);
    cout << dp  [0] << endl;
}

int main()
{
    ///freopen("test.txt", "r", stdin);
    solve();
    return 0;
}
/**
10 2
2
1 -1
3 3
5 -1
8 3
*/

Compilation message (stderr)

walk.cpp: In function 'int get_index(int, int, int, int, int)':
walk.cpp:93:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   93 |     if (left == right)
      |     ^~
walk.cpp:96:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   96 |         int mid = (left + right) / 2;
      |         ^~~
walk.cpp: In function 'int dfs(int)':
walk.cpp:194:1: warning: no return statement in function returning non-void [-Wreturn-type]
  194 | }
      | ^
walk.cpp: In function 'void sweep_line()':
walk.cpp:209:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  209 |     for (int i = 0; i < event.size(); i ++)
      |                     ~~^~~~~~~~~~~~~~
walk.cpp: In function 'int distance_to_end(int)':
walk.cpp:156:1: warning: control reaches end of non-void function [-Wreturn-type]
  156 | }
      | ^
walk.cpp: In function 'std::pair<int, int> get_point(int)':
walk.cpp:173:1: warning: control reaches end of non-void function [-Wreturn-type]
  173 | }
      | ^

• Subtask 1: 0 / 100