QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#94390#6192. Interval ProblemHOLIC#WA 2ms15672kbC++202.0kb2023-04-05 19:26:122023-04-05 19:26:13

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-05 19:26:13]
  • Judged
  • Verdict: WA
  • Time: 2ms
  • Memory: 15672kb
  • [2023-04-05 19:26:12]
  • Submitted

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'