QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#65192 | #4236. Triangular Logs | Sorting# | AC ✓ | 11179ms | 12304kb | C++ | 3.6kb | 2022-11-28 00:15:33 | 2022-11-28 00:15:35 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
const int MX = 1e9 + 3;
const int LM = 60;
const int C = (int)sqrt(N);
#define all(x) (x).begin(), (x).end()
struct Fenwick{
int a[N];
void add(int idx, int val){
idx += 3;
for(; idx < N; idx += idx & -idx)
a[idx] += val;
}
int query(int idx){
idx += 3;
int ans = 0;
for(; idx >= 1; idx -= idx & -idx)
ans += a[idx];
return ans;
}
int query(int l, int r){
return query(r) - query(l - 1);
}
};
int n, q;
array<int, 3> tree[N];
array<int, 5> quer[N];
bool ans[N];
vector<int> x, y;
set<int> s;
Fenwick st;
int query(int l, int r){
if(l > r || r == -1 || l == n)
return 0;
if(st.query(l, r) > LM)
return 1;
auto it = s.lower_bound(l);
vector<int> v;
while(it != s.end() && *it <= r){
v.push_back(tree[y[(*it)]][2]);
++it;
}
sort(all(v));
for(int i = 0; i < (int)v.size() - 2; ++i)
if(v[i] + v[i + 1] > v[i + 2])
return true;
return false;
}
void add(int idx){
int j = tree[x[idx]][1];
s.insert(j);
st.add(j, 1);
}
void rem(int idx){
int j = tree[x[idx]][1];
s.erase(j);
st.add(j, -1);
}
int lower_bound_x(const vector<int> &x, int val){
int l = 0, r = n;
while(l != r){
int mid = (l + r) >> 1;
if(tree[x[mid]][0] >= val)
r = mid;
else
l = mid + 1;
}
return l;
}
int lower_bound_y(const vector<int> &y, int val){
int l = 0, r = n;
while(l != r){
int mid = (l + r) >> 1;
if(tree[y[mid]][1] >= val)
r = mid;
else
l = mid + 1;
}
return l;
}
void compress(){
for(int i = 0; i < n; ++i)
x.push_back(i);
sort(all(x), [&](auto l, auto r){
return tree[l][0] < tree[r][0];
});
for(int i = 0; i < q; ++i){
quer[i][0] = lower_bound_x(x, quer[i][0]);
quer[i][2] = lower_bound_x(x, quer[i][2] + 1) - 1;
}
for(int i = 0; i < n; ++i)
tree[x[i]][0] = i;
for(int i = 0; i < n; ++i)
y.push_back(i);
sort(all(y), [&](auto l, auto r){
return tree[l][1] < tree[r][1];
});
for(int i = 0; i < q; ++i){
quer[i][1] = lower_bound_y(y, quer[i][1]);
quer[i][3] = lower_bound_y(y, quer[i][3] + 1) - 1;
}
for(int i = 0; i < n; ++i)
tree[y[i]][1] = i;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> q;
for(int i = 0; i < n; ++i)
for(int j = 0; j < 3; ++j)
cin >> tree[i][j];
sort(tree, tree + n);
for(int i = 0; i < q; ++i){
for(int j = 0; j < 4; ++j)
cin >> quer[i][j];
quer[i][4] = i;
}
compress();
sort(quer, quer + q, [&](auto l, auto r){
if(l[0] / C == r[0] / C)
return l[2] > r[2];
return l[0] < r[0];
});
int l = 0, r = -1;
for(int i = 0; i < q; ++i){
if(quer[i][0] == n || quer[i][2] == -1){
ans[quer[i][4]] = 0;
continue;
}
for(; r < quer[i][2]; ++r)
add(r + 1);
for(; l > quer[i][0]; --l)
add(l - 1);
for(; r > quer[i][2]; --r)
rem(r);
for(; l < quer[i][0]; ++l)
rem(l);
ans[quer[i][4]] = query(quer[i][1], quer[i][3]);
}
for(int i = 0; i < q; ++i)
cout << ans[i] << "\n";
}
详细
Test #1:
score: 100
Accepted
time: 3ms
memory: 5396kb
input:
9 5 1 3 3 2 3 1 3 3 4 1 2 1 2 2 5 3 2 9 1 1 2 2 1 6 3 1 5 1 1 1 2 1 1 2 2 1 1 1 3 1 2 3 2 1 1 3 3
output:
0 1 0 0 1
result:
ok 5 lines
Test #2:
score: 0
Accepted
time: 3ms
memory: 3460kb
input:
481 1 8 6788 8975 24 6552 2668 26 7948 4730 40 531 9805 110 1914 1916 164 7073 3371 165 6293 7756 170 9946 2003 179 9654 1700 215 6447 2229 221 3149 3030 242 1999 6843 242 5764 3163 249 3716 8634 250 6801 9317 260 2741 4273 282 5436 4836 284 3951 6483 288 4812 76 375 9004 5492 380 5627 5929 391 6385...
output:
1
result:
ok single line: '1'
Test #3:
score: 0
Accepted
time: 3ms
memory: 5468kb
input:
378 1 62730 50925 80731 92666 77280 61521 29236 67032 7889 35986 96802 8763 13313 49918 83582 51842 66775 47834 2286 12925 41106 39790 6698 15243 65145 56379 68496 35570 809 525 39834 16723 48002 77230 16273 16032 52615 7621 77300 92267 82517 39917 13170 89084 77751 45638 23868 49631 7758 71381 5191...
output:
1
result:
ok single line: '1'
Test #4:
score: 0
Accepted
time: 165ms
memory: 10948kb
input:
100000 100000 299999993 206450345 26023928 334281171 300000008 18107965 318653732 299999990 82338399 299999997 393028366 37212808 299999992 208114125 82126189 300000002 303613195 34463905 270033576 299999993 49200970 300000003 249755524 5829381 300000003 367329175 12867359 300000009 337452692 131045...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 100000 lines
Test #5:
score: 0
Accepted
time: 161ms
memory: 11080kb
input:
100000 100000 299999990 299999990 40343876 299999990 299999991 75128878 299999990 299999992 54630219 299999990 299999993 2733654 299999990 299999994 46236519 299999990 299999995 98430004 299999990 299999996 48355189 299999990 299999997 85287882 299999990 299999998 83938086 299999990 299999999 739070...
output:
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
result:
ok 100000 lines
Test #6:
score: 0
Accepted
time: 332ms
memory: 11004kb
input:
100000 100000 586649484 999402721 770254678 406977522 613559 332964690 987164 445493717 518079399 249557488 999424331 597100212 143514230 999205612 56986976 933588533 509797 769263555 696911 930171165 201130067 833170 541105172 912457971 145501 423684829 612968794 999276416 167526939 136454621 70428...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 100000 lines
Test #7:
score: 0
Accepted
time: 333ms
memory: 11004kb
input:
100000 100000 341071 873501571 1101 59980263 526804 9 297715277 999186682 197674 709891830 999005915 346 999712634 250379232 3158 999959502 879534904 11273 253455643 999864444 49222 427866822 999577133 210191465 729566332 999548170 14 657471525 144302 846059 319542083 999756032 6275 219750473 765955...
output:
0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 ...
result:
ok 100000 lines
Test #8:
score: 0
Accepted
time: 10293ms
memory: 12064kb
input:
100000 100000 330451877 499036874 19421 148915905 333179772 5692 556747855 500052531 51199 580265032 499999972 188350435 380806313 500000128 65 500046272 499999847 2336904 496578778 500015254 22900850 499999993 473970765 17403806 499999989 499163205 2 499999946 499999562 19056 671553596 327120722 53...
output:
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
result:
ok 100000 lines
Test #9:
score: 0
Accepted
time: 2ms
memory: 3496kb
input:
44 1 1 1 1 2 2 1 3 3 2 4 4 3 5 5 5 6 6 8 7 7 13 8 8 21 9 9 34 10 10 55 11 11 89 12 12 144 13 13 233 14 14 377 15 15 610 16 16 987 17 17 1597 18 18 2584 19 19 4181 20 20 6765 21 21 10946 22 22 17711 23 23 28657 24 24 46368 25 25 75025 26 26 121393 27 27 196418 28 28 317811 29 29 514229 30 30 832040 3...
output:
0
result:
ok single line: '0'
Test #10:
score: 0
Accepted
time: 3ms
memory: 5504kb
input:
45 1 1 1 1 2 2 1 3 3 2 4 4 3 5 5 5 6 6 8 7 7 13 8 8 21 9 9 34 10 10 55 11 11 89 12 12 144 13 13 233 14 14 377 15 15 610 16 16 987 17 17 1597 18 18 2584 19 19 4181 20 20 6765 21 21 10946 22 22 17711 23 23 28657 24 24 46368 25 25 75025 26 26 121393 27 27 196418 28 28 317811 29 29 514229 30 30 832040 3...
output:
1
result:
ok single line: '1'
Test #11:
score: 0
Accepted
time: 11179ms
memory: 12304kb
input:
100000 100000 51117683 475559198 55 813845469 801994152 34 100675101 138896713 75025 674464384 463090901 55 902054575 869434307 514229 605417726 228399535 377 169256387 179944933 121393 512055115 920070240 3 9910025 214361011 1597 136966996 202823334 5 809276926 864634761 144 349042632 12808782 34 9...
output:
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
result:
ok 100000 lines
Test #12:
score: 0
Accepted
time: 10641ms
memory: 12204kb
input:
100000 100000 22278009 297645636 5702887 216682777 711802229 6765 428165552 28960704 4181 897637309 6584268 701408733 489121330 334310790 46368 82789029 688310692 377 591766279 602483915 2 507641379 304240670 317811 509164606 712250388 75025 507760780 110079699 2 852079642 843093685 75025 472835533 ...
output:
1 1 1 1 0 1 0 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
result:
ok 100000 lines
Test #13:
score: 0
Accepted
time: 179ms
memory: 7540kb
input:
100000 100000 1582278 1577287 1 4746834 1577287 2 7911390 1577287 3 11075946 1577287 5 14240502 1577287 8 17405058 1577287 13 20569614 1577287 1 23734170 1577287 2 26898726 1577287 3 30063282 1577287 5 33227838 1577287 8 36392394 1577287 13 39556950 1577287 1 42721506 1577287 2 45886062 1577287 3 49...
output:
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
result:
ok 100000 lines
Test #14:
score: 0
Accepted
time: 117ms
memory: 7464kb
input:
99990 2222 808609143 791567776 1 808919711 791796567 1 808069792 791902659 2 808104504 791739356 3 808886088 791504796 5 808821181 791960293 8 808449111 792186438 13 808952530 791418710 21 808950482 791838071 34 808524778 792132088 55 809023687 792082261 89 808562602 791380376 144 808076738 79176470...
output:
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
result:
ok 2222 lines
Test #15:
score: 0
Accepted
time: 5206ms
memory: 12128kb
input:
100000 100000 629909712 629909712 398 872281243 872281243 10024809 816785764 816785764 247172 657528859 657528859 53254731 228201517 228201517 2439818 565718267 565718267 28473 443534726 443534726 98059 88387904 88387904 199 186944602 186944602 2169907 415004779 415004779 5 661135835 661135835 2 630...
output:
0 0 0 1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 0 1 0 1 1 1 1 1 0 0 1 0 1 0 1 1 1 1 0 1 0 1 1 1 1 1 1 0 0 1 1 0 1 1 1 0 1 1 0 1 0 0 1 1 1 0 1 1 1 1 1 0 0 1 1 0 0 0 1 0 0 1 1 1 0 1 1 1 1 0 1 1 1 0 0 1 1 1 1 1 0 1 0 1 1 1 1 1 0 1 1 0 0 0 1 0 0 1 0 0 0 1 0 1 1 1 0 1 1 1 0 1 1 0 1 0 1 1 0 0 0 1 1 0 1 1 0 0 1 1 0 ...
result:
ok 100000 lines
Test #16:
score: 0
Accepted
time: 6394ms
memory: 12000kb
input:
100000 100000 491385337 500000000 20 416737373 500000000 871 43347252 500000000 12283172 296433756 500000000 172559 926353666 500000000 73621320 384358430 500000000 569492 151794891 500000000 27446626 485516856 500000000 1162161 833453781 500000000 104 136381889 500000000 601654 944609596 500000000 ...
output:
0 0 1 1 0 1 1 0 1 0 1 1 1 0 1 0 0 0 1 1 0 1 0 0 0 0 1 1 0 0 1 1 0 1 1 0 1 1 0 1 1 1 1 0 0 0 1 1 0 0 1 0 1 0 1 0 1 1 0 0 1 0 0 0 0 0 1 1 1 1 1 1 1 0 0 1 0 0 0 0 1 1 0 1 0 0 0 0 1 0 1 0 0 0 0 0 1 1 0 0 0 0 1 0 1 1 0 1 1 1 0 0 1 1 0 1 1 1 0 1 0 1 0 0 0 1 1 0 1 1 0 0 1 1 0 0 0 1 0 0 0 0 1 0 0 1 0 1 0 0 ...
result:
ok 100000 lines
Test #17:
score: 0
Accepted
time: 146ms
memory: 12168kb
input:
100000 100000 500000000 835730809 8611019 500000000 55914010 23902 500000000 841175146 40133470 500000000 427205129 609 500000000 722589256 35603 500000000 607575657 465243375 500000000 589669151 85667528 500000000 386727444 442780 500000000 772072358 61506 500000000 607134054 1463781 500000000 7349...
output:
1 1 1 0 1 0 0 0 1 0 0 1 0 0 1 0 1 0 1 0 0 0 0 0 1 0 0 1 0 1 0 1 1 1 0 0 1 1 0 1 0 0 1 0 1 1 0 0 1 0 0 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 0 0 1 0 1 1 0 0 1 0 1 0 1 1 1 0 1 0 0 0 1 1 1 0 1 0 1 0 1 0 1 0 1 0 0 0 0 1 0 1 1 0 0 0 1 0 1 0 1 1 0 0 1 0 1 1 1 0 0 1 0 0 1 1 0 0 1 1 1 0 0 0 1 0 0 0 0 1 1 0 0 0 0 ...
result:
ok 100000 lines
Test #18:
score: 0
Accepted
time: 11123ms
memory: 12020kb
input:
100000 100000 559205749 287135929 450126584 758119461 184774699 598200561 414446193 374292451 385550826 358111719 30532876 545952173 709623739 844720071 407013389 263952910 421519775 344566912 811746771 724951475 638700399 300679092 156847316 335763182 181460320 661477907 662719804 280155732 2092322...
output:
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
result:
ok 100000 lines
Test #19:
score: 0
Accepted
time: 3ms
memory: 5580kb
input:
45 2 1 1 1 2 2 1 3 3 2 4 4 3 5 5 5 6 6 8 7 7 13 8 8 21 9 9 34 10 10 55 11 11 89 12 12 144 13 13 233 14 14 377 15 15 610 16 16 987 17 17 1597 18 18 2584 19 19 4181 20 20 6765 21 21 10946 22 22 17711 23 23 28657 24 24 46368 25 25 75025 26 26 121393 27 27 196418 28 28 317811 29 29 514229 30 30 832040 3...
output:
0 1
result:
ok 2 lines
Test #20:
score: 0
Accepted
time: 115ms
memory: 12060kb
input:
100000 100000 129156744 1000000000 292317 1000000000 301262190 26 713069171 1 29401 1000000000 921487600 752 491313490 1 2 384053173 1 6020642 1000000000 532704708 238698 762472640 1 23 1000000000 82407673 14543 994720640 1000000000 5 3211241 1000000000 117626 983507192 1000000000 5904 1000000000 21...
output:
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
result:
ok 100000 lines