QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#749941 | #9765. Repetitive Routes | nicksms# | AC ✓ | 1ms | 5668kb | C++17 | 2.5kb | 2024-11-15 11:35:37 | 2024-11-15 11:35:38 |
Judging History
answer
#include <bits/stdc++.h>
#define endln '\n'
#define print(x) cout << (x) << endln
using namespace std;
using ll = long long;
ll n;
const ll maxN = 4e5 + 5;
ll arr[maxN];
pair<ll, ll> searchArr[maxN];
ll distinct[maxN];
ll ansArr[maxN];
ll ans = 0;
ll leftPos, rightPos;
ll rootN = 650;
struct Query
{
ll l, r, queryNum, blockNum;
};
bool cmp(Query self, Query other)
{
if (self.blockNum < other.blockNum)
{
return true;
}
else if (self.blockNum > other.blockNum)
{
return false;
}
else
{
return self.r < other.r;
}
}
void add(ll index)
{
distinct[arr[index]]++;
if (distinct[arr[index]] == 1)
{
ans++;
}
}
void remove(ll index)
{
distinct[arr[index]]--;
if (distinct[arr[index]] == 0)
{
ans--;
}
}
void update(Query qr)
{
ll l = qr.l, r = qr.r;
while (leftPos < l)
{
remove(leftPos);
leftPos++;
}
while (leftPos > l)
{
leftPos--;
add(leftPos);
}
while (rightPos < r)
{
rightPos++;
add(rightPos);
}
while (rightPos > r)
{
remove(rightPos);
rightPos--;
}
ansArr[qr.queryNum] = ans;
}
void solve()
{
cin >> n;
for (ll i = 0; i < 2 * n; i++)
{
ll ind, x;
cin >> ind >> x;
arr[i] = x;
searchArr[ind].second = i + 1;
if (searchArr[ind].first == 0)
{
searchArr[ind].first = i + 1;
}
}
vector<Query> queries(n);
for (ll i = 1; i <= n; i++)
{
searchArr[i].first--;
searchArr[i].second--;
ll a = searchArr[i].first;
ll b = searchArr[i].second;
ll ind = i - 1;
queries[ind].l = a, queries[ind].r = b;
queries[ind].queryNum = i - 1;
queries[ind].blockNum = a / rootN;
}
sort(queries.begin(), queries.end(), cmp);
leftPos = queries[0].l, rightPos = queries[0].r;
for (ll i = leftPos; i <= rightPos; i++)
{
distinct[arr[i]]++;
if (distinct[arr[i]] == 1)
{
ans++;
}
}
for (Query q : queries)
{
update(q);
}
ll ans = 0;
for (ll i = 1; i <= n; i++)
{
ll distinct = ansArr[i - 1];
ll total = searchArr[i].second - searchArr[i].first + 1;
// cerr << i << " " << distinct << " " << total << endln;
ans += total - distinct;
}
print(ans);
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5620kb
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: 5668kb
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'