QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#763172 | #9765. Repetitive Routes | go_next# | AC ✓ | 0ms | 3872kb | C++20 | 1.5kb | 2024-11-19 18:39:41 | 2024-11-19 18:39:42 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define dbg(A) cerr << #A << " = " << A << '\n';
const int SQ = 400;
struct Query {
int l, r;
Query(int l, int r) : l(l), r(r) {}
const bool operator<(Query &other) const {
return make_pair(l / SQ, r) < make_pair(other.l / SQ, other.r);
}
};
const int N = 2e5 + 5;
int a[N], fq[N], cur;
void add(int i) {
fq[a[i]]++;
if (fq[a[i]] >= 2)cur++;
}
void remove(int i) {
if (fq[a[i]] >= 2)cur--;
fq[a[i]]--;
}
int64_t out;
void moAlgo(vector<Query> &q) {
int curL = 0, curR = -1;
vector<int> ans(q.size());
for (auto &[l, r]: q) {
while (curR < r)
add(++curR);
while (curL > l)
add(--curL);
while (curL < l)
remove(curL++);
while (curR > r)
remove(curR--);
// cerr << l << ' ' << r << ' ' << cur << '\n';
out += cur;
}
}
void solve() {
int n;
cin >> n;
vector<Query> q;
vector<int> L(n + 1 , -1);
for (int i = 0; i < 2 * n; i++) {
int c, l;
cin >> c >> l;
a[i] = l;
if (L[c] == -1)L[c] = i;
else q.push_back({L[c], i});
}
std::sort(q.begin(), q.end());
moAlgo(q);
cout << out << '\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;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3872kb
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: 3624kb
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'