QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#783169 | #5513. Advertisement 2 | phuong2222 | 0 | 55ms | 16532kb | C++20 | 2.3kb | 2024-11-26 00:25:57 | 2024-11-26 00:25:58 |
Judging History
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();
}
Details
Tip: Click on the bar to expand more detailed information
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%