QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#792088#9765. Repetitive Routescry#AC ✓1ms5400kbC++141.8kb2024-11-28 23:41:312024-11-28 23:41:32

Judging History

This is the latest submission verdict.

  • [2024-11-28 23:41:32]
  • Judged
  • Verdict: AC
  • Time: 1ms
  • Memory: 5400kb
  • [2024-11-28 23:41:31]
  • Submitted

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();
}

详细

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'