QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#94396 | #6192. Interval Problem | HOLIC# | WA | 77ms | 19468kb | C++20 | 2.0kb | 2023-04-05 19:41:36 | 2023-04-05 19:41:39 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N = 4e5 + 10;
#define ll long long
#define endl "\n"
struct node{
int l, r, id;
} a[N];
int fa[N], n, m, l1[N], r1[N], num[N];
ll ans[N], val[N];
struct BIT{
int c[N];
void add(int x) {
for(; x <= m; x += x & -x) c[x] ++;
}
int query(int x) {
int ans = 0;
for(; x; x -= x & -x) ans += c[x];
return ans;
}
int query(int l, int r) {
return query(r) - query(l - 1);
}
}L, R;
void work() {
cin >> n;
m = 2 * n;
for(int i = 1; i <= n; i ++) {
cin >> a[i].l >> a[i].r;
a[i].id = i;
l1[i] = a[i].l;
r1[i] = a[i].r;
R.add(a[i].r);
L.add(a[i].l);
}
for(int i = 1; i <= n; i ++) {
num[i] = n - R.query(1, l1[i] - 1) - L.query(r1[i] + 1, m) - 1;
}
sort(a + 1, a + n + 1, [&](node x, node y) {
if(x.l != y.l) return x.l < y.l;
return x.r > y.r;
});
int maxnr = -1, F = 0;
vector<node> b;
for(int i = 1; i <= n; i ++) {
if(maxnr < a[i].r) {
F = a[i].id;
b.push_back(a[i]);
maxnr = a[i].r;
}
fa[a[i].id] = F;
}
ll sum = 0;
int Num = 1;
for(int i = 1; i < b.size(); i ++) {
if(b[i - 1].r < b[i].l) sum = 0, Num = b[i - 1].r + 1;
int num1 = R.query(Num, b[i].l - 1);
sum = sum + 2 * num1;
ans[b[i].id] += sum;
}
sum = 0;
Num = m;
for(int i = (int)(b.size()) - 2; i >= 0; i --) {
if(b[i + 1].l >= b[i].r) sum = 0, Num = b[i + 1].l - 1;
int num1 = L.query(b[i].r + 1, Num);
sum = sum + 2 * num1;
ans[b[i].id] += sum;
}
for(int i = 1; i <= n; i ++) {
val[i] = ans[fa[i]] + num[i] + (num[fa[i]] - num[i]) * 2;
}
for(int i = 1; i <= n; i ++)
cout << val[i] << endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int Case = 1;
while(Case --) work();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 17716kb
input:
5 2 3 6 7 1 9 5 10 4 8
output:
7 5 4 5 5
result:
ok 5 number(s): "7 5 4 5 5"
Test #2:
score: -100
Wrong Answer
time: 77ms
memory: 19468kb
input:
200000 342504 342505 248314 248317 259328 259334 234817 234821 225726 225732 371424 371425 260562 260565 34752 34753 132098 132100 262130 262134 7254 7255 228491 228492 43488 43492 188408 188410 11691 11692 350334 350335 327350 327352 360684 360685 182051 182052 72131 72135 194666 194668 61303 61313...
output:
11 20 21 6 16 37 2 1 1 33 5 0 39 22 6 11 2 17 14 8 2 12 0 1 0 2 48 50 50 6 4 0 30 21 20 11 35 10 5 9 1 16 16 21 8 1 2 58 16 13 28 12 4 26 2 48 0 0 33 20 0 36 4 11 18 20 26 12 2 4 0 51 11 0 1 6 84 7 1 23 3 6 1 57 7 29 16 12 45 58 4 10 27 30 1 0 4 4 0 1 8 3 1 20 55 23 61 5 14 45 73 0 0 0 34 0 23 21 7 ...
result:
wrong answer 1st numbers differ - expected: '12', found: '11'