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

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


გაგზავნის თარიღი: 08.06.2021 00:15:40

ამოცანა: უდიდესი ზრდადი ქვემიმდევრობა

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

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

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







#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

int n, arr[(int)1e6 + 5], prevpos[(int)1e6 + 5];
set<pair<int, int>> val_pos;

int main(){
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i) scanf("%d", &arr[i]);
        val_pos.insert({0, 0});

        for (int i = 1; i <= n; ++i) {
                auto it = val_pos.upper_bound({arr[i], 0});
                if (it != val_pos.end()) {
                        val_pos.erase(it);
                }
                val_pos.insert({arr[i], i});
                prevpos[i] = (--it)->second;
        }

        printf("%ld", val_pos.size() - 1);

        return 0;
}

ტესტები

შემავალი მონაცემები
10
1 4 13 1 6 11 10 8 14 9
გამომავალი მონაცემები
5
თქვენი პასუხი
5
ჩეკერის პასუხი
YES
შემავალი მონაცემები
30
45 3 21 34 3 41 16 37 17 26 26 21 9 46 39 1 27 11 11 39 9 25 1 3 31 26 3 9 19 37
გამომავალი მონაცემები
7
თქვენი პასუხი
7
ჩეკერის პასუხი
YES
შემავალი მონაცემები
100
181 137 155 110 49 5 145 141 86 69 132 3 126 70 121 178 197 3 9 39 173 10 71 51 146 109 131 186 19 41 25 177 130 200 161 12 97 1 61 161 43 51 21 119 151 169 76 196 185 130 193 1 71 31 164 21 53 1 114 104 169 189 145 197 176 121 53 164 59 169 131 15 27...
გამომავალი მონაცემები
15
თქვენი პასუხი
15
ჩეკერის პასუხი
YES
შემავალი მონაცემები
1000
1547 1618 721 169 1500 529 898 100 110 875 1502 12 1282 871 1486 1761 465 743 220 1901 1005 1819 1182 1097 1565 369 333 137 716 1779 626 1333 1961 151 1527 970 1486 1668 733 1816 678 981 585 1781 1564 811 485 318 1102 1201 164 1533 291 1949 1769 109 ...
გამომავალი მონაცემები
56
თქვენი პასუხი
56
ჩეკერის პასუხი
YES
შემავალი მონაცემები
10000
13001 8229 5849 3049 10608 13323 19239 3886 18451 7255 17613 12299 5441 6221 16161 18775 423 18337 3955 4055 13921 876 8191 10974 4189 14899 1851 3237 17172 15943 735 10481 556 12482 12366 15916 409 7586 13309 15726 18113 4954 16737 5837 4881 2817 1...
გამომავალი მონაცემები
196
თქვენი პასუხი
196
ჩეკერის პასუხი
YES
შემავალი მონაცემები
50000
70044 112211 121575 119701 96494 116151 148247 65441 182084 181561 4785 6961 75825 83331 161863 3281 91755 168885 127400 76841 196401 112988 78850 128381 47593 153211 20144 133470 154721 101393 158232 147725 189125 27001 152266 76171 92768 164403 84...
გამომავალი მონაცემები
440
თქვენი პასუხი
440
ჩეკერის პასუხი
YES
შემავალი მონაცემები
100000
89045 170024 172447 100003 147071 47978 105149 145401 83735 93448 187704 184986 19889 9143 71262 51021 81869 160995 102999 18641 198705 50301 85663 51194 93204 69527 50122 89665 71086 68137 92797 126205 7521 137517 20903 141870 108781 35676 128001 ...
გამომავალი მონაცემები
624
თქვენი პასუხი
624
ჩეკერის პასუხი
YES
შემავალი მონაცემები
300000
712503 74275 264391 516914 695152 760433 291169 824576 982561 186551 280735 490521 797917 902785 649209 560708 822071 957964 517921 572011 647625 409494 395035 674161 382854 210429 632785 848885 964929 130971 608393 691673 97303 302551 121025 34692...
გამომავალი მონაცემები
1077
თქვენი პასუხი
1077
ჩეკერის პასუხი
YES
შემავალი მონაცემები
700000
498133 162167 594725 394833 556219 80019 458165 324806 173105 365793 35321 835181 661867 320005 720825 709660 99331 141701 651735 786241 127561 455201 347236 931979 217821 122047 731673 414041 104321 447681 73901 211701 829469 701251 230089 480989 ...
გამომავალი მონაცემები
1668
თქვენი პასუხი
1668
ჩეკერის პასუხი
YES
შემავალი მონაცემები
1000000
932839 958969 149181 353689 97601 172206 155847 619398 211771 701417 545361 388456 4073 398201 542497 21150 611427 139066 94574 493311 109873 443281 411065 759241 38630 925335 866481 328061 177673 77251 170671 817626 977281 112991 638609 35297 915...
გამომავალი მონაცემები
1994
თქვენი პასუხი
1994
ჩეკერის პასუხი
YES