Submission #634564

# Submission time Handle Problem Language Result Execution time Memory
634564 2022-08-24T14:59:33 Z qwerasdfzxcl Sky Walking (IOI19_walk) C++17
Compilation error
0 ms 0 KB
#include "walk.h"
#include <bits/stdc++.h>
#define int long long

using namespace std;
typedef long long ll;
const ll INF = 4e18;
struct Seg{
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> tree[200200];
    int sz;
    void init(int n){sz = n;}
    void update(int x, ll val, int e){
        x += sz;
        for (;x;x>>=1) tree[x].emplace(val, e);
    }
    ll query(int l, int r, int s){
        ++r;
        ll ret = INF;
        for (l+=sz, r+=sz;l<r;l>>=1, r>>=1){
            if (l&1){
                while(!tree[l].empty() && tree[l].top().second < s) tree[l].pop();
                if (!tree[l].empty()) ret = min(ret, tree[l].top().first);
                l++;
            }
            if (r&1){
                --r;
                while(!tree[r].empty() && tree[r].top().second < s) tree[r].pop();
                if (!tree[r].empty()) ret = min(ret, tree[r].top().first);
            }
        }
        return ret;
    }
}tree1, tree2;

struct Line{
    int l, r, y, i;
    Line(){}
    Line(int _l, int _r, int _y, int _i): l(_l), r(_r), y(_y), i(_i) {}
    bool operator < (const Line &L) const{
        return tie(l, y) < tie(L.l, L.y);
    }
}E[100100];
ll D[100100];

ll myabs(ll x){return x<0?-x:x;}
ll dist(ll x1, ll y1, ll x2, ll y2){return myabs(x1-x2) + myabs(y1-y2);}

vector<int> cy;
int getidx(int y){return lower_bound(cy.begin(), cy.end(), y) - cy.begin();}

long long min_distance(std::vector<signed> x, std::vector<signed> h, std::vector<signed> l, std::vector<signed> r, std::vector<signed> y, signed s, signed g) {
	int n = x.size(), m = l.size();
	if (n==1) return 0;
	for (int i=0;i<m;i++) E[i] = Line(x[l[i]], x[r[i]], y[i], i);
	sort(E, E+m);

	cy = y;
	cy.push_back(0);
	sort(cy.begin(), cy.end());
	cy.erase(unique(cy.begin(), cy.end()), cy.end());
	tree1.init(m+1);
	tree2.init(m+1);

	tree1.update(0, dist(0, 0, 1e9, 1e9), 0);
	fill(D, D+m, INF);
	//printf("ok\n");

    for (int i=0;i<m;){
        int j = i;
        for (;j<m;j++) if (E[i].l!=E[j].l) break;

        for (int k=i;k<j;k++){
            D[k] = min(D[k], tree1.query(0, getidx(E[k].y), E[k].l) - dist(E[k].l, E[k].y, 1e9, 1e9));
        }
        for (int k=j-1;k>=i;k--){
            D[k] = min(D[k], tree2.query(getidx(E[k].y)+1, m, E[k].l) - dist(E[k].l, E[k].y, 1e9, 0));
        }

        for (int k=i;k<j;k++){
            tree1.update(getidx(E[k].y), D[k] + dist(E[k].l, E[k].y, 1e9, 1e9), E[k].r);
            tree2.update(getidx(E[k].y), D[k] + dist(E[k].l, E[k].y, 1e9, 0), E[k].r);
        }

        i = j;
    }

    //for (int i=0;i<m;i++) printf(" %d %d %d -> %lld\n", E[i].l, E[i].r, E[i].y, D[i]);

    ll ans = INF;
    for (int i=0;i<m;i++) if (E[i].r==x[g]) ans = min(ans, D[i] + dist(E[i].l, E[i].y, x[g], 0));
    return ans>=INF/2?-1:ans;
}

Compilation message

walk.cpp: In function 'long long int min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:57:7: error: no match for 'operator=' (operand types are 'std::vector<long long int>' and 'std::vector<int>')
   57 |  cy = y;
      |       ^
In file included from /usr/include/c++/10/vector:72,
                 from walk.h:4,
                 from walk.cpp:1:
/usr/include/c++/10/bits/vector.tcc:198:5: note: candidate: 'std::vector<_Tp, _Alloc>& std::vector<_Tp, _Alloc>::operator=(const std::vector<_Tp, _Alloc>&) [with _Tp = long long int; _Alloc = std::allocator<long long int>]'
  198 |     vector<_Tp, _Alloc>::
      |     ^~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/bits/vector.tcc:199:42: note:   no known conversion for argument 1 from 'std::vector<int>' to 'const std::vector<long long int>&'
  199 |     operator=(const vector<_Tp, _Alloc>& __x)
      |               ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
In file included from /usr/include/c++/10/vector:67,
                 from walk.h:4,
                 from walk.cpp:1:
/usr/include/c++/10/bits/stl_vector.h:709:7: note: candidate: 'std::vector<_Tp, _Alloc>& std::vector<_Tp, _Alloc>::operator=(std::vector<_Tp, _Alloc>&&) [with _Tp = long long int; _Alloc = std::allocator<long long int>]'
  709 |       operator=(vector&& __x) noexcept(_Alloc_traits::_S_nothrow_move())
      |       ^~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:709:26: note:   no known conversion for argument 1 from 'std::vector<int>' to 'std::vector<long long int>&&'
  709 |       operator=(vector&& __x) noexcept(_Alloc_traits::_S_nothrow_move())
      |                 ~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_vector.h:730:7: note: candidate: 'std::vector<_Tp, _Alloc>& std::vector<_Tp, _Alloc>::operator=(std::initializer_list<_Tp>) [with _Tp = long long int; _Alloc = std::allocator<long long int>]'
  730 |       operator=(initializer_list<value_type> __l)
      |       ^~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:730:46: note:   no known conversion for argument 1 from 'std::vector<int>' to 'std::initializer_list<long long int>'
  730 |       operator=(initializer_list<value_type> __l)
      |                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~