QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#762859#9765. Repetitive Routeszezoo050#AC ✓0ms5696kbC++201.3kb2024-11-19 17:00:022024-11-19 17:00:06

Judging History

This is the latest submission verdict.

  • [2024-11-19 17:00:06]
  • Judged
  • Verdict: AC
  • Time: 0ms
  • Memory: 5696kb
  • [2024-11-19 17:00:02]
  • Submitted

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;
}

詳細信息

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'