QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#783169#5513. Advertisement 2phuong22220 55ms16532kbC++202.3kb2024-11-26 00:25:572024-11-26 00:25:58

Judging History

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

  • [2024-11-26 00:25:58]
  • 评测
  • 测评结果:0
  • 用时:55ms
  • 内存:16532kb
  • [2024-11-26 00:25:57]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxN = 5e5 + 5;
int id[maxN],a[maxN],b[maxN],n;
vector<int> v;
struct Tsegment_tree
{
    ll st[2 * maxN];
    void build()
    {
        for (int i = 0;i <= 2 * n;++i) st[i] = 1e18;
    }
    void update(int i,ll val)
    {
        for (st[i += n] = min(st[i],val);i > 1;i >>= 1)
            st[i >> 1] = min(st[i],st[i ^ 1]);
    }
    ll get(int l,int r)
    {
        ++r;
        ll res = 1e18;
        for (l += n,r += n;l < r;l >>= 1,r >>= 1)
        {
            if (l & 1) res = min(res,st[l++]);
            if (r & 1) res = min(res,st[--r]);
        }
        return res;
    }
    void build1()
    {
        for (int i = 0;i <= 2 * n;++i) st[i] = -1e18;
    }
    void update1(int i,ll val)
    {
        for (st[i += n] = max(st[i],val);i > 1;i >>= 1)
            st[i >> 1] = max(st[i],st[i ^ 1]);
    }
    ll get1(int l,int r)
    {
        ++r;
        ll res = -1e18;
        for (l += n,r += n;l < r;l >>= 1,r >>= 1)
        {
            if (l & 1) res = max(res,st[l++]);
            if (r & 1) res = max(res,st[--r]);
        }
        return res;
    }
}
s1,s2;
bool cmp(int x,int y)
{
    return b[x] > b[y];
}
void input()
{
    cin >> n;
    for (int i = 1;i <= n;++i)
    {
        cin >> a[i] >> b[i];
        id[i] = i;
        v.push_back(a[i]);
    }
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
}
int getid(int x)
{
    return lower_bound(v.begin(),v.end(),x) - v.begin() + 1;
}
void solve()
{
    sort(id + 1,id + n + 1,cmp);
    s1.build();
    s2.build1();
    //s1.update(2,b[8] - a[8]);
    //cout << s1.get(1,9) << "\n";
    int res = 0;
    for (int i = 1;i <= n;++i)
    {
        int x = id[i];
        int idx = getid(a[x]);
        //cout << idx << " " << s1.get(1,idx) << " " << s2.get1(idx,n) << " " << x << "\n";
        if (s1.get(idx,n) <= a[x] - b[x] || s2.get1(1,idx) >= a[x] + b[x]) continue;
        ++res;
        //cerr << x << "\n";
        s1.update(idx,a[x] - b[x]);
        s2.update1(idx,b[x] + a[x]);

    }
    cout << res;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
//    freopen("B.inp","r",stdin);
//    freopen("B.out","w",stdout);
    input();
    solve();
}

详细

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 55ms
memory: 16532kb

input:

128800
9199612 51970557
152303663 51970557
658020283 51970557
305169975 51970557
647937895 51970557
162441995 51970557
664350717 51970557
128813867 51970557
815800777 51970557
422654970 51970557
5325941 51970557
919605369 51970557
775929588 51970557
957253076 51970557
441558150 51970557
730596606 51...

output:

1242

result:

wrong answer 1st lines differ - expected: '116732', found: '1242'

Subtask #2:

score: 0
Wrong Answer

Test #9:

score: 23
Accepted
time: 0ms
memory: 11860kb

input:

3
231636235 354089104
228392707 930073348
587735804 575683740

output:

2

result:

ok single line: '2'

Test #10:

score: 23
Accepted
time: 0ms
memory: 11844kb

input:

2
44803615 325394921
960290812 913042209

output:

2

result:

ok single line: '2'

Test #11:

score: 23
Accepted
time: 2ms
memory: 11856kb

input:

16
358962202 959156048
292228464 457977429
286504790 688097514
10235865 287544591
543037593 223202351
281739475 678894125
340538778 135823278
523049160 699098750
632448464 27592532
678838907 280282008
232201876 610344934
372201424 580697311
534022553 149440684
396794335 231096472
386573567 674797431...

output:

1

result:

ok single line: '1'

Test #12:

score: 23
Accepted
time: 1ms
memory: 9736kb

input:

16
991478601 586353863
727677584 413218995
848190574 721774939
337154838 587621991
326181535 330546474
885714927 902337871
321925936 254469460
389203245 713455202
269046070 768322315
614176036 221983130
199199666 945777980
333801969 632191948
426251079 645513607
230568723 962651792
817646607 6209057...

output:

3

result:

ok single line: '3'

Test #13:

score: 23
Accepted
time: 1ms
memory: 9864kb

input:

16
259716405 81082178
865953834 204158972
701456061 326495636
534687353 313425011
649435476 973258810
655435866 100458236
842552753 181656857
473079491 116991153
2508936 173927847
405046133 391068638
302771733 495790124
35966251 515357032
272182509 442914085
348221691 938487780
990378664 943640991
2...

output:

3

result:

ok single line: '3'

Test #14:

score: 23
Accepted
time: 1ms
memory: 11840kb

input:

16
750613470 787418986
170979548 365164484
538034539 608096710
860751449 225707539
484373402 547435035
940351136 194668865
912301765 93898337
458896779 93991117
604496090 637207865
887366195 906979783
557233961 724709014
79115098 854994617
46404315 744331005
915505818 998759323
415682887 70000722
24...

output:

3

result:

ok single line: '3'

Test #15:

score: 23
Accepted
time: 1ms
memory: 9740kb

input:

16
4 4
12 10
7 1
14 9
5 1
7 4
6 2
11 12
11 8
7 7
1 16
1 7
7 11
10 1
5 9
16 14

output:

4

result:

ok single line: '4'

Test #16:

score: 0
Wrong Answer
time: 1ms
memory: 11784kb

input:

16
14 11
15 15
2 2
9 11
12 3
1 2
5 6
3 8
11 6
6 8
16 8
7 13
14 15
3 9
11 13
5 12

output:

4

result:

wrong answer 1st lines differ - expected: '5', found: '4'

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Skipped

Dependency #1:

0%