QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#850322 | #9765. Repetitive Routes | rand123 | AC ✓ | 1ms | 3852kb | C++14 | 1.9kb | 2025-01-10 00:49:16 | 2025-01-10 00:49:17 |
Judging History
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'