QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#94390 | #6192. Interval Problem | HOLIC# | WA | 2ms | 15672kb | C++20 | 2.0kb | 2023-04-05 19:26:12 | 2023-04-05 19:26:13 |
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] - 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: 0
Wrong Answer
time: 2ms
memory: 15672kb
input:
5 2 3 6 7 1 9 5 10 4 8
output:
6 4 3 4 4
result:
wrong answer 1st numbers differ - expected: '7', found: '6'