QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#762859 | #9765. Repetitive Routes | zezoo050# | AC ✓ | 0ms | 5696kb | C++20 | 1.3kb | 2024-11-19 17:00:02 | 2024-11-19 17:00:06 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int tree[4 * N];
int n;
void up(int widx, int node = 1, int l = 1, int r = 2 * n) {
if (l == r) {
tree[node] = 1 - tree[node];
return;
}
int mid = (l + r) / 2;
if (widx <= mid)
up(widx, node * 2, l, mid);
else up(widx, node * 2 + 1, mid + 1, r);
tree[node] = tree[node * 2] + tree[node * 2 + 1];
}
int query(int wl, int wr, int node = 1, int l = 1, int r = 2 * n) {
if (wl <= l and r <= wr) {
return tree[node];
}
if (r < wl or l > wr)
return 0;
int mid = (l + r) / 2;
return query(wl, wr, node * 2, l, mid) + query(wl, wr, node * 2 + 1, mid + 1, r);
}
int pos1[N];
int pos2[N];
void solve() {
cin >> n;
long long sum = 0;
for (int i = 1; i <= 2 * n; i++) {
int c, l;
cin >> c >> l;
if (pos1[l]) {
up(pos1[l]);
}
pos1[l] = i;
up(pos1[l]);
if (pos2[c]) {
sum += i - pos2[c] + 1 - query(pos2[c], i);
} else {
pos2[c] = i;
}
}
cout<<sum<<'\n';
}
int32_t main() {
std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 5584kb
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: 0ms
memory: 5696kb
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'