QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#65192#4236. Triangular LogsSorting#AC ✓11179ms12304kbC++3.6kb2022-11-28 00:15:332022-11-28 00:15:35

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-11-28 00:15:35]
  • 评测
  • 测评结果:AC
  • 用时:11179ms
  • 内存:12304kb
  • [2022-11-28 00:15:33]
  • 提交

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