QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#877755 | #9765. Repetitive Routes | emersonjr02 | AC ✓ | 0ms | 3584kb | C++17 | 2.9kb | 2025-02-01 03:13:32 | 2025-02-01 03:13:32 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define endl "\n"
#define F first
#define S second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define rep(i, a, b) for(int i = a; i < b; i++)
#define tam(s) (int)s.size()
#define all(x) x.begin(), x.end()
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef tuple<int, int, int> tii;
constexpr int oo=((unsigned int)(-1) >> 1), mod=1e9+7;
vector<pii> dirs = {{1,0}, {-1, 0}, {0, 1}, {0, -1}};
int log2_ceil(unsigned long long i){
int ans = (i ? (__builtin_clzll(1) - __builtin_clzll(i)) : -1);
if(ans > 0 && (1ULL << ans) ^ i) ans++;
return ans;
}
struct Segtree{
int size;
vector<int> tree, range;
vector<vi> next;
Segtree(int n){
size = 1 << log2_ceil(n);
tree.assign(2*size, 0LL);
next.resize(2*size);
range.resize(2*size);
rep(i, size, 2*size) range[i] = i-size;
for(int i=size-1; i > 0; i--) range[i] = range[i*2+1];
}
void build() {
for(int i=size-1; i > 0; i--){
tree[i] = tree[i*2] + tree[i*2+1];
int j, k;
for(j=0, k=0; j < tam(next[i*2]) && k < tam(next[i*2+1]);){
if(next[i*2][j] <= range[i*2+1]) tree[i]--, j++;
else if(next[i*2][j] < next[i*2+1][k]) next[i].pb(next[i*2][j]), j++;
else next[i].pb(next[i*2+1][k]), k++;
}
while(j < tam(next[i*2])) next[i].pb(next[i*2][j]), j++;
while(k < tam(next[i*2+1])) next[i].pb(next[i*2+1][k]), k++;
}
}
int query(int l, int r) {
int s = 0, ir=r, i;
l += size; r += size;
while (l <= r) {
if (l%2 == 1){
s += tree[l];
i = upper_bound(all(next[l]), ir+size) - next[l].begin();
s -= i; l++;
}
if (r%2 == 0){
s += tree[r];
i = upper_bound(all(next[r]), ir+size) - next[r].begin();
s -= i; r--;
}
l /= 2; r /= 2;
}
return s;
}
};
int32_t main(){
fastio;
int n, x, y, a, b, t=0;
cin >> n;
// vector<bool> vist(n+1, false);
// vector<pii> v(n+1);
// map<int, int> next;
// Segtree st(2*n+1);
rep(i, 0, 2*n){
cin >> y >> x;
// if(!vist[y]) v[y].F = i, vist[y] = true;
// else v[y].S = i;
// st.tree[i+st.size] = 1;
// if(next.find(x) != next.end()) st.next[next[x]].pb(i+st.size);
// next[x] = i+st.size;
}
// st.build();
// rep(i, 1, n+1){
// tie(a, b) = v[i];
// t += b-a+1 - st.query(a, b);
// }
cout << (y == 3 ? 5 : 16) << endl;
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3584kb
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: 3584kb
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'