QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#94395 | #6192. Interval Problem | HOLIC# | WA | 91ms | 21476kb | C++20 | 2.0kb | 2023-04-05 19:37:06 | 2023-04-05 19:37:07 |
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;
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 ++) {
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: 3ms
memory: 17676kb
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: 91ms
memory: 21476kb
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:
57501 993228 777969 330354 399994 1857067 399996 1 132097 951421 785485 0 1469489 611578 399996 350335 2 78621 582036 327866 205332 522586 0 82673 0 2 1168292 1558530 458094 908726 24172 0 1192900 258269 22418 53867 1388315 25072 399997 799981 1 167210 1081816 765817 34368 285149 198210 1627122 7999...
result:
wrong answer 1st numbers differ - expected: '12', found: '57501'