QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#792088 | #9765. Repetitive Routes | cry# | AC ✓ | 1ms | 5400kb | C++14 | 1.8kb | 2024-11-28 23:41:31 | 2024-11-28 23:41:32 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int INF = 1E9; const ll INFLL = 1E18;
const int DX[8] = {1, 0, -1, 0, -1, -1, 1, 1};
const int DY[8] = {0, 1, 0, -1, -1, 1, -1, 1};
const int MAX = 4E5 + 10;
int lg[MAX];
struct Sparse {
int n; int k;
vector<vector<array<int, 2>>> sparse;
Sparse() {}
Sparse(vector<array<int, 2>>& a) {
n = a.size(); k = lg[n] + 1;
sparse.resize(n, vector<array<int, 2>>(k));
for(int i = 0; i < n; i++) {
sparse[i][0] = a[i];
}
for(int i = 1; i < k; i++) {
for(int j = 0; j + (1 << i) - 1 < n; j++) {
sparse[j][i] = min(sparse[j][i - 1], sparse[j + (1 << (i - 1))][i - 1]);
}
}
}
int query(int l, int r) {
int v = lg[r - l + 1];
return abs(min(sparse[l][v], sparse[r - (1 << v) + 1][v])[0]);
}
};
int n;
void solve() {
for(int i = 2; i < MAX; i++) {
lg[i] = lg[i / 2] + 1;
}
cin >> n;
vector<array<int, 2>> a(2 * n);
vector<array<int, 2>> inds(n, {-1, -1});
for(int i = 0; i < 2 * n; i++) {
cin >> a[i][1] >> a[i][0];
a[i][0]--; a[i][1]--;
if(inds[a[i][1]][0] == -1) {
inds[a[i][1]][0] = i;
} else {
inds[a[i][1]][1] = i;
}
}
Sparse sparseMin(a);
vector<array<int, 2>> aa = a;
for(int i = 0; i < 2 * n; i++) {
a[i][0] = -a[i][0];
}
Sparse sparseMax(a);
vector<ll> movements(2 * n);
for(int i = 0; i < 2 * n; i++) {
if(i + 1 < 2 * n) {
movements[i] = max(abs(a[i + 1][0] - a[i][0]), 1);
}
if(i) {
movements[i] += movements[i - 1];
}
}
ll wochien = 0;
for(int i = 0; i < n; i++) {
ll tot = movements[inds[i][1] - 1] - (!inds[i][0] ? 0 : movements[inds[i][0] - 1]);
wochien += tot - (sparseMax.query(inds[i][0], inds[i][1]) - sparseMin.query(inds[i][0], inds[i][1]));
}
cout << wochien << "\n";
}
int main() {
cin.tie(0) -> sync_with_stdio(0);
solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 5400kb
input:
4 1 1 2 2 2 3 3 2 4 1 4 2 1 3 3 4
output:
5
result:
ok single line: '5'
Test #2:
score: 0
Accepted
time: 1ms
memory: 5336kb
input:
4 1 1 2 1 3 1 4 1 4 1 3 1 2 1 1 1
output:
16
result:
ok single line: '16'