QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#850322#9765. Repetitive Routesrand123AC ✓1ms3852kbC++141.9kb2025-01-10 00:49:162025-01-10 00:49:17

Judging History

This is the latest submission verdict.

  • [2025-01-10 00:49:17]
  • Judged
  • Verdict: AC
  • Time: 1ms
  • Memory: 3852kb
  • [2025-01-10 00:49:16]
  • Submitted

answer

#include <bits/stdc++.h>
#define pii pair<int,int>
#define pb push_back
#define ll long long
#define MOD 1000000007
#define all(x) x.begin(),x.end()
#define MOD2 998244353
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
struct SegmentTree{
    vector<ll> tree;
    SegmentTree(int n){
        tree.resize(4*n);
    }
    ll update(int node, int left, int right, int pos, int val){
        if (left==right){
            return tree[node]=val;
        }
        int mid = (left+right)/2;
        ll l = pos<=mid?update(2*node+1,left,mid,pos,val):tree[2*node+1];
        ll r = pos>mid?update(2*node+2,mid+1,right,pos,val):tree[2*node+2];
        return tree[node]=l+r;
    }
    ll query(int node, int left, int right, int arrLeft, int arrRight){
        if (arrLeft>right || arrRight < left){
            return 0;
        }
        if (arrLeft>=left && arrRight<=right){
            return tree[node];
        }
        int mid = (arrLeft+arrRight)/2;
        return query(2*node+1,left,right,arrLeft,mid) + query(2*node+2,left,right,mid+1,arrRight);
    }
};
void solve(int cas){  
    int n; cin>>n;
    int sz = 4*n;
    SegmentTree segTree(sz);
    vector<int> cpos(n,-1), lpos(2*n, -1);
    ll res = 0, ct = 0;
    for (int i = 0; i < 2*n; i++){
        int c,l; cin>>c>>l; --c; --l;
        if (lpos[l]!=-1){
            res += segTree.query(0,0,lpos[l],0,sz-1);
        }
        if (cpos[c]!=-1){
            segTree.update(0,0,sz-1,cpos[c],0);
        }
        else{
            segTree.update(0,0,sz-1,ct,1);
            cpos[c] = ct;
        }
        lpos[l] = ct;
        ct++;
    }
    cout << res << '\n';
}
int main(){
    int t=1;
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //cin>>t;
    for (int i = 1; i<=t; i++){
        solve(i);
    }
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3672kb

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: 3852kb

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'