QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#749941#9765. Repetitive Routesnicksms#AC ✓1ms5668kbC++172.5kb2024-11-15 11:35:372024-11-15 11:35:38

Judging History

This is the latest submission verdict.

  • [2024-11-15 11:35:38]
  • Judged
  • Verdict: AC
  • Time: 1ms
  • Memory: 5668kb
  • [2024-11-15 11:35:37]
  • Submitted

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'