QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#763172#9765. Repetitive Routesgo_next#AC ✓0ms3872kbC++201.5kb2024-11-19 18:39:412024-11-19 18:39:42

Judging History

This is the latest submission verdict.

  • [2024-11-19 18:39:42]
  • Judged
  • Verdict: AC
  • Time: 0ms
  • Memory: 3872kb
  • [2024-11-19 18:39:41]
  • Submitted

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'