QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#94395#6192. Interval ProblemHOLIC#WA 91ms21476kbC++202.0kb2023-04-05 19:37:062023-04-05 19:37:07

Judging History

你现在查看的是最新测评结果

  • [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:37:07]
  • 评测
  • 测评结果:WA
  • 用时:91ms
  • 内存:21476kb
  • [2023-04-05 19:37:06]
  • 提交

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'