#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
using tii = tuple<int,int,int>;
using ll = long long;
const int nmax = 2e5 + 5;
const ll inf = 2e10 + 5;
//#warning vectorii sa ii indexezi de la 1
int h[nmax], v[nmax]; int L, C;
int get(int a) { return (a < 0? h[-a] : v[a]); }
namespace G {
vector< vector<pii> > g;
vector<ll> dp;
vector<ll> occ;
void reset() {
g.clear();
dp.clear();
}
int newnode() {
g.push_back(vector<pii>());
dp.push_back(-1);
occ.push_back(0);
return g.size() - 1;
}
void addedge(int x, int y, int c) { g[x].push_back({y, c}); }
int startdfs(int node) {
if(occ[node] != 0)
return dp[node];
occ[node] = 1;
for(auto [a, b] : g[node])
dp[node] = max((ll)startdfs(a) + b, dp[node]);
return dp[node];
}
}
int start(int x, int y, bool hor, bool dir) {
//cerr << hor << ' ' << dir << '\n';
//auto cmp = [&](tii a, tii b) { return get(get<0>(a)) > get(get<0>(b)); };
//priority_queue<tuple<int,int,int>, vector< tuple<int,int,int> >, decltype(cmp) > heap(cmp);
auto cmp = [&](int a, int b) { return get(a) < get(b); };
map<int, vector<pii>, decltype(cmp) > heap(cmp);
G::reset();
int source, sink = G::newnode(); // == 0
int l[2] = {x, y}, r[2] = {x, y};
if(hor)
heap[-x].push_back({y, source = G::newnode()}),
(dir == 0? l[1]-- : r[1]++);
else
heap[y].push_back({x, source = G::newnode()}),
(dir == 0? l[0]-- : r[0]++);
int node;
while(!heap.empty()) {
x = heap.begin()->first;
//cerr << x << '\n';
int dir = 0, target = get(x);
if(x < 0)
dir = 1;
while(l[dir] > 0 && (dir == 0? h : v)[l[dir]] < target)
l[dir]--;
while(r[dir] <= (dir == 0? L : C) && (dir == 0? h : v)[r[dir]] < target)
r[dir]++;
//cerr << " > " << x << ' ' << get(x) << ' ' << l[dir] << ' ' << r[dir] << '\n';
int lnode = sink, rnode = sink;
if(l[dir] != 0)
heap[(dir == 0? -1 : 1) * l[dir]].push_back({abs(x), lnode = G::newnode()});
if(r[dir] <= (dir == 0? L : C))
heap[(dir == 0? -1 : 1) * r[dir]].push_back({abs(x), rnode = G::newnode()});
auto &vec = heap[x];
for(auto [coord, atrnode] : vec) {
G::addedge(atrnode, lnode, abs(coord - l[dir]));
G::addedge(atrnode, rnode, abs(coord - r[dir]));
}
vec.clear();
heap.erase(heap.begin());
}
//cerr << G::startdfs(source) << '\n';
//cerr << '\n';
return G::startdfs(source);
}
int main() {
cin.tie(0);
ios_base::sync_with_stdio(0);
cin >> L >> C;
int q;
cin >> q;
for(int i = 1; i <= L; i++)
cin >> h[i];
for(int i = 1; i <= C; i++)
cin >> v[i];
for(int i = 0; i < q; i++) {
int x, y;
cin >> x >> y;
cout << max({start(x, y, 1, 1), start(x, y, 0, 0)
, start(x, y, 1, 0), start(x, y, 0, 1)}) << '\n';
//cerr << "-------------------\n";
}
}
Compilation message
abduction2.cpp: In function 'int G::startdfs(int)':
abduction2.cpp:38:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
38 | for(auto [a, b] : g[node])
| ^
abduction2.cpp: In function 'int start(int, int, bool, bool)':
abduction2.cpp:78:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
78 | for(auto [coord, atrnode] : vec) {
| ^
abduction2.cpp:59:7: warning: unused variable 'node' [-Wunused-variable]
59 | int node;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
536 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
