ამოხსნების სტატუსი

ამ გვერდზე თქვენ იხილავთ გაგზავნილი ამოხსნების სტატუსს.


გაგზავნის თარიღი: 27.03.2020 01:52:39

ამოცანა: დაბალანსებული მწკრივი

მომხმარებელი: qartveli

ვერდიქტი: სრული ამოხსნა

შეფასება: 100.0 ქულა







#include <bits/stdc++.h>

using namespace std;

struct Node {
    int minVal = INT_MAX, maxVal = INT_MIN;
    Node * left = NULL, * right = NULL;
};

void add(Node * &base, int value, int index, int first, int last) { // last is the index after the last position
    if (last - first == 1) {
        base->minVal = value;
        base->maxVal = value;
        return;
    }

    int middle = (first + last) / 2;
    if (index < middle) {
        if (!base->left) base->left = new Node();
        add(base->left, value, index, first, middle);
        if (base->left->minVal < base->minVal) base->minVal = base->left->minVal;
        if (base->left->maxVal > base->maxVal) base->maxVal = base->left->maxVal;
    }
    else {
        if (!base->right) base->right = new Node();
        add(base->right, value, index, middle, last);
        if (base->right->minVal < base->minVal) base->minVal = base->right->minVal;
        if (base->right->maxVal > base->maxVal) base->maxVal = base->right->maxVal;
    }
}

pair<int, int> getMinMax(Node * &base, int qFirst, int qLast, int first, int last) {
    if (!base) return {INT_MAX, INT_MIN};
    if (qFirst <= first && last-1 <= qLast) return {base->minVal, base->maxVal}; // fully inside target interval
    if (qLast < first || last-1 < qFirst) return {INT_MAX, INT_MIN}; // fully outside target interval

    pair<int, int> leftMinMax = getMinMax(base->left, qFirst, qLast, first, (first + last) / 2);
    pair<int, int> rightMinMax = getMinMax(base->right, qFirst, qLast, (first + last) / 2, last);
    return {min(leftMinMax.first, rightMinMax.first), max(leftMinMax.second, rightMinMax.second)};
}

int main() {
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);

    int n, m;
    cin >> n >> m;

    int nComplete; // filled to next power of 2
    for (nComplete = 1; nComplete < n; nComplete <<= 1);

    Node * root = new Node();

    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        add(root, x, i, 0, nComplete);
    }

    for (int i = 0; i < m; ++i) {
        int qFirst, qLast;
        cin >> qFirst >> qLast;
        --qFirst, --qLast;
        pair<int, int> minMax = getMinMax(root, qFirst, qLast, 0, nComplete);
        cout << minMax.second - minMax.first << endl;
    }

    return 0;
}

ტესტები

შემავალი მონაცემები
6 3
1
7
3
4
2
5
1 5
4 6
2 2
გამომავალი მონაცემები
6
3
0
თქვენი პასუხი
6
3
0
ჩეკერის პასუხი
YES
შემავალი მონაცემები
50000 180000
909565
265669
462459
374047
886781
405296
859801
453426
993389
279701
283105
663045
182637
294898
411061
498411
693937
607479
129754
768013
631729
373523
884975
399104
416396
111691
530031
168598
722597
39481
690247
910527
397053
58939
369140
...
გამომავალი მონაცემები
998616
951402
875187
973364
947832
962536
999438
903515
866435
999868
885337
937934
963294
947887
999868
999770
732456
960106
996893
967214
948670
897022
985720
984647
999770
999868
986730
999843
999868
600696
976881
931546
999868
916064
948798
885181
9321...
თქვენი პასუხი
998616
951402
875187
973364
947832
962536
999438
903515
866435
999868
885337
937934
963294
947887
999868
999770
732456
960106
996893
967214
948670
897022
985720
984647
999770
999868
986730
999843
999868
600696
976881
931546
999868
916064
948798
885181
9321...
ჩეკერის პასუხი
YES
შემავალი მონაცემები
100 300
170789
314332
967885
616030
356631
979466
290649
411053
62943
711745
980369
774978
680773
985115
952911
950465
649137
399904
659755
82566
349185
899515
370785
158637
291008
691619
151521
240205
740288
99387
662931
664085
512320
599539
291737
548809...
გამომავალი მონაცემები
983086
983086
968520
983086
983086
934470
970281
688817
908208
908208
983086
946833
983086
983086
769198
934909
983086
780030
946833
983086
970077
970077
946833
922172
910841
910841
970077
902549
593641
966893
983086
970077
934470
980909
946833
981348
6409...
თქვენი პასუხი
983086
983086
968520
983086
983086
934470
970281
688817
908208
908208
983086
946833
983086
983086
769198
934909
983086
780030
946833
983086
970077
970077
946833
922172
910841
910841
970077
902549
593641
966893
983086
970077
934470
980909
946833
981348
6409...
ჩეკერის პასუხი
YES
შემავალი მონაცემები
2000 1000
50259
530150
848841
731482
269409
738897
263713
724772
579277
517495
594513
808663
75391
955729
218081
894335
339305
171051
391025
971202
491000
321841
29137
875645
618234
230847
914673
175959
705004
659489
228625
827399
734657
808912
770041
6784...
გამომავალი მონაცემები
982607
997221
941231
957329
979345
973244
995446
973210
957742
957742
995446
992119
995446
964456
995446
974470
954998
995446
879638
901882
864298
997221
986271
994649
982886
977280
997890
981019
995446
985020
930979
825464
979780
997221
997221
993434
9314...
თქვენი პასუხი
982607
997221
941231
957329
979345
973244
995446
973210
957742
957742
995446
992119
995446
964456
995446
974470
954998
995446
879638
901882
864298
997221
986271
994649
982886
977280
997890
981019
995446
985020
930979
825464
979780
997221
997221
993434
9314...
ჩეკერის პასუხი
YES
შემავალი მონაცემები
10000 20000
850292
151763
997825
771257
486521
502177
150031
835265
307985
734747
161188
169308
968065
705889
107627
827632
498561
492382
521798
278721
370233
356385
975145
594276
208661
514170
942070
155318
398949
378620
170849
437205
166245
709054
241457...
გამომავალი მონაცემები
999621
978552
970422
940477
994602
997844
951950
797592
997683
963465
959615
940997
995516
998601
995820
724711
920117
996482
999621
999278
977912
933284
999048
892513
999645
997559
998597
996154
998597
999645
827453
999645
999621
920229
889700
999621
9996...
თქვენი პასუხი
999621
978552
970422
940477
994602
997844
951950
797592
997683
963465
959615
940997
995516
998601
995820
724711
920117
996482
999621
999278
977912
933284
999048
892513
999645
997559
998597
996154
998597
999645
827453
999645
999621
920229
889700
999621
9996...
ჩეკერის პასუხი
YES
შემავალი მონაცემები
30000 50000
728805
408029
960748
289367
268057
6011
295949
474573
787432
255161
56161
795749
305795
652121
868685
971115
413369
652666
88081
345042
551265
230184
314197
112679
50976
133479
741681
874058
938681
802285
285889
679269
452417
67631
99053
803174...
გამომავალი მონაცემები
999745
939830
972296
999483
999636
998971
983156
999745
999978
992748
918906
972196
970036
910984
969554
999202
999726
969206
969796
999428
999967
974798
943936
949132
995084
999617
998956
999745
997431
957099
999483
998792
976763
998362
998557
999067
9999...
თქვენი პასუხი
999745
939830
972296
999483
999636
998971
983156
999745
999978
992748
918906
972196
970036
910984
969554
999202
999726
969206
969796
999428
999967
974798
943936
949132
995084
999617
998956
999745
997431
957099
999483
998792
976763
998362
998557
999067
9999...
ჩეკერის პასუხი
YES
შემავალი მონაცემები
40000 50000
39437
140021
290819
595945
80153
774177
569245
165889
495329
896043
179020
190849
848809
329548
886401
736091
912661
854013
188108
512699
688831
441835
287062
892949
514159
902873
814900
641961
853331
176331
351401
675828
193393
939353
934869
8...
გამომავალი მონაცემები
910864
885132
917014
960031
999988
787175
978638
966588
959097
897432
886664
999946
999718
999411
999946
979690
999929
999967
998384
895774
999738
999926
972300
848383
999946
999875
996234
999929
581152
999875
999967
998617
967056
695535
941444
951721
9104...
თქვენი პასუხი
910864
885132
917014
960031
999988
787175
978638
966588
959097
897432
886664
999946
999718
999411
999946
979690
999929
999967
998384
895774
999738
999926
972300
848383
999946
999875
996234
999929
581152
999875
999967
998617
967056
695535
941444
951721
9104...
ჩეკერის პასუხი
YES
შემავალი მონაცემები
50000 50000
579057
146097
759263
15570
257889
886754
86387
418979
725417
934803
252103
791337
569529
921526
872103
781193
340254
180760
796817
905317
632117
422707
361807
802221
255023
148305
56193
665438
414150
519931
595633
664941
997823
99944
863265
920...
გამომავალი მონაცემები
959668
999909
975937
940759
849838
999929
962507
999929
999909
966663
987916
925130
966730
999888
999934
999909
980335
990376
976536
919202
989048
999784
999836
964877
982045
963874
954448
995619
993848
999929
999800
984960
880769
999933
646828
983550
9994...
თქვენი პასუხი
959668
999909
975937
940759
849838
999929
962507
999929
999909
966663
987916
925130
966730
999888
999934
999909
980335
990376
976536
919202
989048
999784
999836
964877
982045
963874
954448
995619
993848
999929
999800
984960
880769
999933
646828
983550
9994...
ჩეკერის პასუხი
YES
შემავალი მონაცემები
50000 100000
408803
726885
346353
499204
103874
825229
658597
601921
785923
31073
111817
29231
882183
270373
384897
279317
870565
212869
393718
2641
563417
870675
510147
66928
375029
164437
930817
392416
847025
376073
444003
398061
308546
128705
746267
310...
გამომავალი მონაცემები
999074
999973
971807
999269
999973
924240
999590
973042
569991
931568
939616
970653
561418
983611
869558
999973
991686
937598
967962
999973
999626
970001
991797
961836
999973
965314
945378
999621
956876
972764
999346
872248
999350
999617
999703
999973
9993...
თქვენი პასუხი
999074
999973
971807
999269
999973
924240
999590
973042
569991
931568
939616
970653
561418
983611
869558
999973
991686
937598
967962
999973
999626
970001
991797
961836
999973
965314
945378
999621
956876
972764
999346
872248
999350
999617
999703
999973
9993...
ჩეკერის პასუხი
YES
შემავალი მონაცემები
50000 150000
759125
782954
149021
480008
574843
838689
646317
753313
649651
800227
131514
625602
30572
438405
756396
46445
903667
998969
269063
552401
816959
168434
233547
521751
315123
744393
630374
172555
410301
919741
647974
774528
518237
120917
982645
...
გამომავალი მონაცემები
720806
999776
967374
967345
976858
999916
998078
999880
998864
999776
904787
972565
999916
999916
983604
999916
999916
710758
949231
999916
982757
999888
967671
468351
852436
999880
982673
999886
996660
984409
989442
947325
703181
902144
934028
980715
9998...
თქვენი პასუხი
720806
999776
967374
967345
976858
999916
998078
999880
998864
999776
904787
972565
999916
999916
983604
999916
999916
710758
949231
999916
982757
999888
967671
468351
852436
999880
982673
999886
996660
984409
989442
947325
703181
902144
934028
980715
9998...
ჩეკერის პასუხი
YES