QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#94399 | #6192. Interval Problem | HOLIC# | WA | 75ms | 23576kb | C++20 | 2.0kb | 2023-04-05 19:59:56 | 2023-04-05 19:59:58 |
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]) - L.query(r1[i], 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);
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, 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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 17776kb
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: 75ms
memory: 23576kb
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'