QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#94389 | #6192. Interval Problem | HOLIC# | TL | 5ms | 13576kb | C++20 | 2.1kb | 2023-04-05 19:18:35 | 2023-04-05 19:18:37 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N = 4e5 + 10;
#define ll long long
struct node{
int l, r, id;
} a[N];
int fa[N], n, m, l1[N], r1[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);
}
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;
for(int i = 1; i < b.size(); i ++) {
int num1 = R.query(1, b[i].l - 1);
sum = sum + 2 * num1;
if(b[i - 1].r < b[i].l) sum = 0;
ans[b[i].id] += sum;
}
sum = 0;
for(int i = (int)b.size() - 2; i >= 0; i --) {
int num1 = L.query(b[i].r + 1, m);
sum = sum + 2 * num1;
if(b[i + 1].l > b[i].r) sum = 0;
ans[b[i].id] += sum;
}
for(int i = 1; i <= n; i ++) {
int l = l1[i];
int r = r1[i];
int pa = fa[i];
int pl = l1[pa];
int pr = r1[pa];
int num1 = n - R.query(1, l - 1) - L.query(r + 1, n) - 1;
int num2 = n - R.query(1, pl - 1) - L.query(pr + 1, n) - 1;
val[i] = ans[pa] + num1 + (num2 - num1) * 2;
}
for(int i = 1; i <= n; i ++)
cout << val[i] - 1<< 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: 5ms
memory: 13576kb
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
Time Limit Exceeded
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:
157499 1093226 877967 430352 499992 1957065 499994 99999 232095 1051419 885483 99998 1569487 711576 499994 450333 100000 178619 682034 427864 305330 622584 99998 182671 99998 100000 1268290 1658528 558092 1008724 124170 99998 1292898 358267 122416 153865 1488313 125070 499995 899979 99999 267208 118...