結果
| 問題 | No.2743 Twisted Lattice |
| ユーザー |
 The Forsaking
|
| 提出日時 | 2025-01-22 19:34:56 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 1,903 ms / 3,000 ms |
| コード長 | 5,794 bytes |
| コンパイル時間 | 3,550 ms |
| コンパイル使用メモリ | 136,232 KB |
| 実行使用メモリ | 49,380 KB |
| 最終ジャッジ日時 | 2025-01-22 19:35:19 |
| 合計ジャッジ時間 | 15,287 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 8 |
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:165:42: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
165 | for (int i = 1; i < k + 1; i++) scanf("%d%d", &e[i].x, &e[i].y), num.push_back(e[i].y), e[i].id = i;
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
ソースコード
#include <iostream>
#include <sstream>
#include <iomanip>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <vector>
#include <queue>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <ctime>
#include <assert.h>
#include <deque>
#include <list>
#include <stack>
using namespace std;
#define is_mul_overflow(a, b) \
((b != 0) && (a > LLONG_MAX / b || a < LLONG_MIN / b))
typedef pair<long long, int> pli;
typedef pair<int, long long> pil;
typedef pair<long long , long long> pll;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef pair<int, pii> piii;
typedef pair<int, long long > pil;
typedef pair<long long, pii> plii;
typedef pair<double, int> pdi;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ull, ull> puu;
typedef long double ld;
const int N = 2000086, MOD = 998244353, INF = 0x3f3f3f3f, MID = 333;
const long double EPS = 1e-8;
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
// int dx[8] = {1, 1, 0, -1, -1, -1, 0, 1}, dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};
// int dx[8] = {2, 1, -1, -2, -2, -1, 1, 2}, dy[8] = {1, 2, 2, 1, -1, -2, -2, -1};
int n, m, cnt;
int w[N];
vector<ll> num;
ll res;
ll lowbit(ll x) { return x & -x; }
ll lcm(ll a, ll b) { return a / __gcd(a, b) * b; }
inline double rand(double l, double r) { return (double)rand() / RAND_MAX * (r - l) + l; }
inline ll qmi(ll a, ll b, ll c) { ll res = 1; while (b) { if (b & 1) res = res * a % c; a = a * a % c; b >>= 1; } return res; }
inline ll qmi(ll a, ll b) { ll res = 1; while (b) { if (b & 1) res *= a; a *= a; b >>= 1; } return res; }
inline double qmi(double a, ll b) { double res = 1; while (b) { if (b & 1) res *= a; a *= a; b >>= 1; } return res; }
// inline ll C(ll a, ll b) { if (a < b) return 0; if (b > a - b) b = a - b; ll res = 1; for (ll i = 1, j = a; i <= b; i++, j--) { res = res * (j % MOD) % MOD; res = res * qmi(i, MOD - 2, MOD) % MOD; } return res; }
inline ll C(ll a, ll b, int* c) { if (a < b) return 0; ll res = 1; for (ll j = a, i = 1; i < b + 1; i++, j--) res *= j; for (ll j = a, i = 1; i < b + 1; i++, j--) res /= i; return res; }
inline int find(int x) { return lower_bound(num.begin(), num.end(), x) - num.begin(); }
struct Point {
int x, y, id;
bool operator<(const Point& t) const {
return x < t.x;
}
}e[N];
struct Node {
int l, r;
ll minl, minr;
}tr[N];
int k;
ll ans[N];
void pushup(Node& u, Node& l, Node& r) {
u.l = l.l, u.r = r.r;
u.minl = min(r.minl, l.minl);
u.minr = min(l.minr, r.minr);
}
inline void pushup(int u) { pushup(tr[u], tr[u << 1], tr[u << 1 | 1]); }
void build(int u, int l, int r) {
if (l == r) tr[u] = { l, r, (ll)1e13, (ll)1e13 };
else {
tr[u] = {l, r};
int mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
pushup(u);
}
}
Node query(int u, int l, int r) {
if (tr[u].l >= l && tr[u].r <= r) return tr[u];
int mid = tr[u].l + tr[u].r >> 1;
if (l <= mid && r > mid) {
Node res, ll = query(u << 1, l, r), rr = query(u << 1 | 1, l, r);
pushup(res, ll, rr);
return res;
}
if (l <= mid) return query(u << 1, l, r);
return query(u << 1 | 1, l, r);
}
void modifyl(int u, int x, ll v) {
if (tr[u].l == tr[u].r) tr[u].minl = min(tr[u].minl, v);
else {
int mid = tr[u].l + tr[u].r >> 1;
if (x <= mid) modifyl(u << 1, x, v);
else modifyl(u << 1 | 1, x, v);
pushup(u);
}
}
void modifyr(int u, int x, ll v) {
if (tr[u].l == tr[u].r) tr[u].minr = min(tr[u].minr, v);
else {
int mid = tr[u].l + tr[u].r >> 1;
if (x <= mid) modifyr(u << 1, x, v);
else modifyr(u << 1 | 1, x, v);
pushup(u);
}
}
inline void solve() {
map<int, set<int> > ma;
for (int i = 1; i < k + 1; i++) ma[e[i].y].insert(e[i].x);
for (int i = 1; i < k + 1; i++)
for (int y = e[i].y - 1; y <= e[i].y + 1; y++)
if (ma.count(y)) {
if (y == e[i].y) ma[y].erase(e[i].x);
auto it = ma[y].upper_bound(e[i].x);
if (it != ma[y].end()) ans[e[i].id] = min(ans[e[i].id], (ll)*it - e[i].x + (ll)abs(y - e[i].y) * e[i].x);
if (it != ma[y].begin()) {
it--;
ans[e[i].id] = min(ans[e[i].id], (ll)e[i].x - *it + (ll)abs(y - e[i].y) * (*it));
}
if (y == e[i].y) ma[y].insert(e[i].x);
}
build(1, 0, num.size() - 1);
for (int i = 1; i < k + 1; i++) {
int p = find(e[i].y);
auto u = query(1, 0, p);
ans[e[i].id] = min(ans[e[i].id], u.minl + e[i].x + e[i].y);
u = query(1, p, num.size() - 1);
ans[e[i].id] = min(ans[e[i].id], u.minr + e[i].x - e[i].y);
modifyl(1, p, (ll)-e[i].y - e[i].x + (e[i].x - 1) * 2);
modifyr(1, p, (ll)e[i].y - e[i].x + (e[i].x - 1) * 2);
}
build(1, 0, num.size() - 1);
for (int i = k; i; i--) {
int p = find(e[i].y);
auto u = query(1, 0, p);
ans[e[i].id] = min(ans[e[i].id], u.minl - e[i].x + e[i].y + (e[i].x - 1) * 2);
u = query(1, p, num.size() - 1);
ans[e[i].id] = min(ans[e[i].id], u.minr - e[i].x - e[i].y + (e[i].x - 1) * 2);
modifyl(1, p, -e[i].y + e[i].x);
modifyr(1, p, e[i].y + e[i].x);
}
for (int i = 1; i < k + 1; i++) printf("%lld\n", ans[i]);
}
int main() {
cin >> n >> m >> k;
for (int i = 1; i < k + 1; i++) scanf("%d%d", &e[i].x, &e[i].y), num.push_back(e[i].y), e[i].id = i;
sort(num.begin(), num.end());
num.erase(unique(num.begin(), num.end()), num.end());
sort(e + 1, e + k + 1);
memset(ans, 0x3f, sizeof(ll) * (k + 10));
solve();
return 0;
}