QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#379338 | #8573. Slothful Secretary | ucup-team1516# | WA | 1444ms | 47372kb | C++17 | 5.4kb | 2024-04-06 17:11:11 | 2024-04-06 17:11:12 |
Judging History
answer
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) { return (ull)rng() % B; }
// 0-indexed
template <typename T> struct BIT {
int n;
vector<T> bit, ary;
BIT(int n = 0) : n(n), bit(n + 1), ary(n) {}
T operator[](int k) { return ary[k]; }
// [0, i)
T sum(int i) {
T res = 0;
for (; i > 0; i -= (i & -i)) {
res += bit[i];
}
return res;
}
// [l, r)
T sum(int l, int r) { return sum(r) - sum(l); }
void add(int i, T a) {
ary[i] += a;
i++;
for (; i <= n; i += (i & -i)) {
bit[i] += a;
}
}
int lower_bound(T k) { // k <= sum(res)
if (k <= 0) return 0;
int res = 0, i = 1;
while ((i << 1) <= n)
i <<= 1;
for (; i; i >>= 1) {
if (res + i <= n and bit[res + i] < k) {
k -= bit[res += i];
}
}
return res;
}
// The 2nd UC Stage 9: Qinhuangdao - I
// 円環状で見たときに bit[i]+bit[i-1]+...+bit[j] を求める
T sum_cyc(int i, int j) {
if (j <= i) return sum(j, i + 1);
else return sum(0, i + 1) + sum(j, n);
}
// The 2nd UC Stage 9: Qinhuangdao - I
// 円環状で見たときに bit[i]+bit[i-1]+...+bit[j] >= k となる最近の j と左辺の総和を求める
// 雑にlog2つ
pair<int, T> lower_bound_cyc(int j, T k) {
T prefix = sum(j + 1);
if (prefix < k) {
k -= prefix;
int l = 0, r = n;
while (r - l > 1) {
int mid = (l + r) / 2;
T s = sum(mid, n);
if (s >= k) {
l = mid;
} else {
r = mid;
}
}
return {l, prefix + sum(l, n)};
} else {
int l = 0, r = j + 1;
while (r - l > 1) {
int mid = (l + r) / 2;
T s = sum(mid, j + 1);
if (s >= k) {
l = mid;
} else {
r = mid;
}
}
return {l, sum(l, j + 1)};
}
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
cin >> n >> q;
BIT<int> bit(n + 5);
BIT<ll> seg(n + 5);
set<int> sd;
for (int i = 0; i < n; ++i) {
bit.add(i, 1);
seg.add(i, i);
sd.insert(i);
}
vector<int> deg(n);
for (int i = 0; i < n; ++i) {
deg[i] = n - 1 - i;
}
int res = n;
set<pair<int, int>> st;
while (q--) {
int x, y;
cin >> x >> y;
x -= 1, y -= 1;
if (st.find({x, y}) == st.end()) {
st.insert({x, y});
} else {
st.erase(st.find({x, y}));
swap(x, y);
}
// deg[x] -= 1, deg[y] += 1
vector<int> v;
{
auto it = sd.lower_bound(deg[x]);
for (int i = 0; i < 2; ++i) {
if (it == sd.end()) break;
v.push_back(*it);
it++;
}
it = sd.lower_bound(deg[x]);
for (int i = 0; i < 2; ++i) {
v.push_back(*it);
if (it == sd.begin()) break;
it--;
}
}
{
auto it = sd.lower_bound(deg[y]);
for (int i = 0; i < 2; ++i) {
if (it == sd.end()) break;
v.push_back(*it);
it++;
}
it = sd.lower_bound(deg[y]);
for (int i = 0; i < 2; ++i) {
v.push_back(*it);
if (it == sd.begin()) break;
it--;
}
}
v.push_back(deg[x] - 1);
v.push_back(deg[y] + 1);
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
auto check = [&](int i) -> bool {
if (bit[i] == 0) return false;
ll low_cnt = bit.sum(i);
ll high_cnt = n - low_cnt;
ll sum = (ll)(n - 1) * (ll)n / 2;
ll low_sum = seg.sum(i);
ll high_sum = sum - low_sum;
// cout << low_cnt << " " << high_cnt << " " << sum << " " << low_sum << " "
// << high_cnt
// << endl;
high_sum -= high_cnt * (high_cnt - 1) / 2;
// cout << " " << high_sum << " " << low_cnt * high_cnt << endl;
return high_sum >= low_cnt * high_cnt;
};
for (int j : v)
if (check(j)) res -= 1;
bit.add(deg[x], -1);
seg.add(deg[x], -deg[x]);
if (bit[deg[x]] == 0) sd.erase(deg[x]);
bit.add(deg[y], -1);
seg.add(deg[y], -deg[y]);
if (bit[deg[y]] == 0) sd.erase(deg[y]);
deg[x] -= 1, deg[y] += 1;
bit.add(deg[x], 1);
seg.add(deg[x], deg[x]);
if (bit[deg[x]] == 1) sd.insert(deg[x]);
bit.add(deg[y], 1);
seg.add(deg[y], deg[y]);
if (bit[deg[y]] == 1) sd.insert(deg[y]);
for (int j : v)
if (check(j)) res += 1;
cout << res << "\n";
}
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 1444ms
memory: 47372kb
input:
500000 500000 111236 111238 400537 400538 14798 14799 480138 480140 99901 99904 169041 169045 20969 20970 111098 111100 245492 245493 25296 25300 21736 21739 415491 415495 222594 222595 162236 162238 362422 362425 422694 422695 339973 339974 241678 241680 192401 192403 125627 125629 261473 261474 10...
output:
499998 499998 499998 499996 499993 499990 499990 499988 499988 499985 499982 499979 499979 499977 499974 499974 499974 499972 499970 499968 499968 499965 499965 499965 499965 499965 499965 499962 499959 499956 499953 499951 499951 499949 499946 499944 499942 499940 499938 499935 499932 499930 499927...
result:
wrong answer 6th numbers differ - expected: '499989', found: '499990'