oj.uz

Submission #535521

# Submission time Handle Problem Language Result Execution time Memory
535521 2022-03-10T12:32:27 Z Vladth11 Boat (APIO16_boat) C++14
9 / 100
 2000 ms 5988 KB 
#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "

using namespace std;
typedef long long ll;
typedef pair <ll, ll> pii;
typedef pair <long double, pii> muchie;

const ll NMAX = 501;
const ll VMAX = 1000001;
const ll INF = (1LL << 60);
const ll MOD = 1000000007;
const ll BLOCK = 1000000;
const ll nr_of_bits = 21;

vector <pii> polls;

pii v[NMAX * 2];
pii intervals[NMAX * 2];
ll m;

ll precalc[] = {1, 641102369, 578095319, 5832229, 259081142, 974067448, 316220877, 690120224, 251368199, 980250487, 682498929, 134623568, 95936601, 933097914, 167332441, 598816162, 336060741, 248744620, 626497524, 288843364, 491101308, 245341950, 565768255, 246899319, 968999, 586350670, 638587686, 881746146, 19426633, 850500036, 76479948, 268124147, 842267748, 886294336, 485348706, 463847391, 544075857, 898187927, 798967520, 82926604, 723816384, 156530778, 721996174, 299085602, 323604647, 172827403, 398699886, 530389102, 294587621, 813805606, 67347853, 497478507, 196447201, 722054885, 228338256, 407719831, 762479457, 746536789, 811667359, 778773518, 27368307, 438371670, 59469516, 5974669, 766196482, 606322308, 86609485, 889750731, 340941507, 371263376, 625544428, 788878910, 808412394, 996952918, 585237443, 1669644, 361786913, 480748381, 595143852, 837229828, 199888908, 526807168, 579691190, 145404005, 459188207, 534491822, 439729802, 840398449, 899297830, 235861787, 888050723, 656116726, 736550105, 440902696, 85990869, 884343068, 56305184, 973478770, 168891766, 804805577, 927880474, 876297919, 934814019, 676405347, 567277637, 112249297, 44930135, 39417871, 47401357, 108819476, 281863274, 60168088, 692636218, 432775082, 14235602, 770511792, 400295761, 697066277, 421835306, 220108638, 661224977, 261799937, 168203998, 802214249, 544064410, 935080803, 583967898, 211768084, 751231582, 972424306, 623534362, 335160196, 243276029, 554749550, 60050552, 797848181, 395891998, 172428290, 159554990, 887420150, 970055531, 250388809, 487998999, 856259313, 82104855, 232253360, 513365505, 244109365, 1559745, 695345956, 261384175, 849009131, 323214113, 747664143, 444090941, 659224434, 80729842, 570033864, 664989237, 827348878, 195888993, 576798521, 457882808, 731551699, 212938473, 509096183, 827544702, 678320208, 677711203, 289752035, 66404266, 555972231, 195290384, 97136305, 349551356, 785113347, 83489485, 66247239, 52167191, 307390891, 547665832, 143066173, 350016754, 917404120, 296269301, 996122673, 23015220, 602139210, 748566338, 187348575, 109838563, 574053420, 105574531, 304173654, 542432219, 34538816, 325636655, 437843114, 630621321, 26853683, 933245637, 616368450, 238971581, 511371690, 557301633, 911398531, 848952161, 958992544, 925152039, 914456118, 724691727, 636817583, 238087006, 946237212, 910291942, 114985663, 492237273, 450387329, 834860913, 763017204, 368925948, 475812562, 740594930, 45060610, 806047532, 464456846, 172115341, 75307702, 116261993, 562519302, 268838846, 173784895, 243624360, 61570384, 481661251, 938269070, 95182730, 91068149, 115435332, 495022305, 136026497, 506496856, 710729672, 113570024, 366384665, 564758715, 270239666, 277118392, 79874094, 702807165, 112390913, 730341625, 103056890, 677948390, 339464594, 167240465, 108312174, 839079953, 479334442, 271788964, 135498044, 277717575, 591048681, 811637561, 353339603, 889410460, 839849206, 192345193, 736265527, 316439118, 217544623, 788132977, 618898635, 183011467, 380858207, 996097969, 898554793, 335353644, 54062950, 611251733, 419363534, 965429853, 160398980, 151319402, 990918946, 607730875, 450718279, 173539388, 648991369, 970937898, 500780548, 780122909, 39052406, 276894233, 460373282, 651081062, 461415770, 358700839, 643638805, 560006119, 668123525, 686692315, 673464765, 957633609, 199866123, 563432246, 841799766, 385330357, 504962686, 954061253, 128487469, 685707545, 299172297, 717975101, 577786541, 318951960, 773206631, 306832604, 204355779, 573592106, 30977140, 450398100, 363172638, 258379324, 472935553, 93940075, 587220627, 776264326, 793270300, 291733496, 522049725, 579995261, 335416359, 142946099, 472012302, 559947225, 332139472, 499377092, 464599136, 164752359, 309058615, 86117128, 580204973, 563781682, 954840109, 624577416, 895609896, 888287558, 836813268, 926036911, 386027524, 184419613, 724205533, 403351886, 715247054, 716986954, 830567832, 383388563, 68409439, 6734065, 189239124, 68322490, 943653305, 405755338, 811056092, 179518046, 825132993, 343807435, 985084650, 868553027, 148528617, 160684257, 882148737, 591915968, 701445829, 529726489, 302177126, 974886682, 241107368, 798830099, 940567523, 11633075, 325334066, 346091869, 115312728, 473718967, 218129285, 878471898, 180002392, 699739374, 917084264, 856859395, 435327356, 808651347, 421623838, 105419548, 59883031, 322487421, 79716267, 715317963, 429277690, 398078032, 316486674, 384843585, 940338439, 937409008, 940524812, 947549662, 833550543, 593524514, 996164327, 987314628, 697611981, 636177449, 274192146, 418537348, 925347821, 952831975, 893732627, 1277567, 358655417, 141866945, 581830879, 987597705, 347046911, 775305697, 125354499, 951540811, 247662371, 343043237, 568392357, 997474832, 209244402, 380480118, 149586983, 392838702, 309134554, 990779998, 263053337, 325362513, 780072518, 551028176, 990826116, 989944961, 155569943, 596737944, 711553356, 268844715, 451373308, 379404150, 462639908, 961812918, 654611901, 382776490, 41815820, 843321396, 675258797, 845583555, 934281721, 741114145, 275105629, 666247477, 325912072, 526131620, 252551589, 432030917, 554917439, 818036959, 754363835, 795190182, 909210595, 278704903, 719566487, 628514947, 424989675, 321685608, 50590510, 832069712, 198768464, 702004730, 99199382, 707469729, 747407118, 302020341, 497196934, 5003231, 726997875, 382617671, 296229203, 183888367, 703397904, 552133875, 732868367, 350095207, 26031303, 863250534, 216665960, 561745549, 352946234, 784139777, 733333339, 503105966, 459878625, 803187381, 16634739, 180898306, 68718097, 985594252, 404206040, 749724532, 97830135, 611751357, 31131935, 662741752, 864326453, 864869025, 167831173, 559214642, 718498895, 91352335, 608823837, 473379392, 385388084, 152267158, 681756977, 46819124, 313132653, 56547945, 442795120, 796616594, 256141983, 152028387, 636578562, 385377759, 553033642, 491415383, 919273670, 996049638, 326686486, 160150665, 141827977, 540818053, 693305776, 593938674, 186576440, 688809790, 565456578, 749296077, 519397500, 551096742, 696628828, 775025061, 370732451, 164246193, 915265013, 457469634, 923043932, 912368644, 777901604, 464118005, 637939935, 956856710, 490676632, 453019482, 462528877, 502297454, 798895521, 100498586, 699767918, 849974789, 811575797, 438952959, 606870929, 907720182, 179111720, 48053248, 508038818, 811944661, 752550134, 401382061, 848924691, 764368449, 34629406, 529840945, 435904287, 26011548, 208184231, 446477394, 206330671, 366033520, 131772368, 185646898, 648711554, 472759660, 523696723, 271198437, 25058942, 859369491, 817928963, 330711333, 724464507, 437605233, 701453022, 626663115, 281230685, 510650790, 596949867, 295726547, 303076380, 465070856, 272814771, 538771609, 48824684, 951279549, 939889684, 564188856, 48527183, 201307702, 484458461, 861754542, 326159309, 181594759, 668422905, 286273596, 965656187, 44135644, 359960756, 936229527, 407934361, 267193060, 456152084, 459116722, 124804049, 262322489, 920251227, 816929577, 483924582, 151834896, 167087470, 490222511, 903466878, 361583925, 368114731, 339383292, 388728584, 218107212, 249153339, 909458706, 322908524, 202649964, 92255682, 573074791, 15570863, 94331513, 744158074, 196345098, 334326205, 9416035, 98349682, 882121662, 769795511, 231988936, 888146074, 137603545, 582627184, 407518072, 919419361, 909433461, 986708498, 310317874, 373745190, 263645931, 256853930, 876379959, 702823274, 147050765, 308186532, 175504139, 180350107, 797736554, 606241871, 384547635, 273712630, 586444655, 682189174, 666493603, 946867127, 819114541, 502371023, 261970285, 825871994, 126925175, 701506133, 314738056, 341779962, 561011609, 815463367, 46765164, 49187570, 188054995, 957939114, 64814326, 933376898, 329837066, 338121343, 765215899, 869630152, 978119194, 632627667, 975266085, 435887178, 282092463, 129621197, 758245605, 827722926, 201339230, 918513230, 322096036, 547838438, 985546115, 852304035, 593090119, 689189630, 555842733, 567033437, 469928208, 212842957, 117842065, 404149413, 155133422, 663307737, 208761293, 206282795, 717946122, 488906585, 414236650, 280700600, 962670136, 534279149, 214569244, 375297772, 811053196, 922377372, 289594327, 219932130, 211487466, 701050258, 398782410, 863002719, 27236531, 217598709, 375472836, 810551911, 178598958, 247844667, 676526196, 812283640, 863066876, 857241854, 113917835, 624148346, 726089763, 564827277, 826300950, 478982047, 439411911, 454039189, 633292726, 48562889, 802100365, 671734977, 945204804, 508831870, 398781902, 897162044, 644050694, 892168027, 828883117, 277714559, 713448377, 624500515, 590098114, 808691930, 514359662, 895205045, 715264908, 628829100, 484492064, 919717789, 513196123, 748510389, 403652653, 574455974, 77123823, 172096141, 819801784, 581418893, 15655126, 15391652, 875641535, 203191898, 264582598, 880691101, 907800444, 986598821, 340030191, 264688936, 369832433, 785804644, 842065079, 423951674, 663560047, 696623384, 496709826, 161960209, 331910086, 541120825, 951524114, 841656666, 162683802, 629786193, 190395535, 269571439, 832671304, 76770272, 341080135, 421943723, 494210290, 751040886, 317076664, 672850561, 72482816, 493689107, 135625240, 100228913, 684748812, 639655136, 906233141, 929893103, 277813439, 814362881, 562608724, 406024012, 885537778, 10065330, 60625018, 983737173, 60517502, 551060742, 804930491, 823845496, 727416538, 946421040, 678171399, 842203531, 175638827, 894247956, 538609927, 885362182, 946464959, 116667533, 749816133, 241427979, 871117927, 281804989, 163928347, 563796647, 640266394, 774625892, 59342705, 256473217, 674115061, 918860977, 322633051, 753513874, 393556719, 304644842, 767372800, 161362528, 754787150, 627655552, 677395736, 799289297, 846650652, 816701166, 687265514, 787113234, 358757251, 701220427, 607715125, 245795606, 600624983, 10475577, 728620948, 759404319, 36292292, 491466901, 22556579, 114495791, 647630109, 586445753, 482254337, 718623833, 763514207, 66547751, 953634340, 351472920, 308474522, 494166907, 634359666, 172114298, 865440961, 364380585, 921648059, 965683742, 260466949, 117483873, 962540888, 237120480, 620531822, 193781724, 213092254, 107141741, 602742426, 793307102, 756154604, 236455213, 362928234, 14162538, 753042874, 778983779, 25977209, 49389215, 698308420, 859637374, 49031023, 713258160, 737331920, 923333660, 804861409, 83868974, 682873215, 217298111, 883278906, 176966527, 954913, 105359006, 390019735, 10430738, 706334445, 315103615, 567473423, 708233401, 48160594, 946149627, 346966053, 281329488, 462880311, 31503476, 185438078, 965785236, 992656683, 916291845, 881482632, 899946391, 321900901, 512634493, 303338827, 121000338, 967284733, 492741665, 152233223, 165393390, 680128316, 917041303, 532702135, 741626808, 496442755, 536841269, 131384366, 377329025, 301196854, 859917803, 676511002, 373451745, 847645126, 823495900, 576368335, 73146164, 954958912, 847549272, 241289571, 646654592, 216046746, 205951465, 3258987, 780882948, 822439091, 598245292, 869544707, 698611116};

unordered_map <ll, ll> _fact;

ll lgput(ll n, ll p) {
    ll r = 1;
    while(p) {
        if(p % 2) {
            r *= n;
            r %= MOD;
        }
        n *= n;
        n %= MOD;
        p /= 2;
    }
    return r;
}

ll invmod(ll x) {
    return lgput(x, MOD - 2);
}

ll fact(ll x) {
    if(_fact.find(x) != _fact.end()) {
        return _fact[x];
    }
    ll r = precalc[x / BLOCK];
    for(ll i = x / BLOCK * BLOCK + 1; i <= x; i++) {
        r *= i;
        r %= MOD;
    }
    return _fact[x] = r;
}

ll comb(ll a, ll b) {
    return (fact(a) * invmod(fact(b))) % MOD * invmod(fact(a - b)) % MOD;
}

ll dp[501][2001];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll n, i, j;
    cin >> n;
    for(i = 1; i <= n; i++) {
        cin >> v[i].first >> v[i].second;
        polls.push_back({v[i].first, 0});
        polls.push_back({v[i].second, 1});
    }
    sort(polls.begin(), polls.end());
    ll open = 0;
    for(i = 0; i < polls.size(); i++) {
        if(polls[i].second == 0)
            open++;
        else
            open--;
        if(polls[i].second == 0 && intervals[m].first != polls[i].first) {
            if(open == 1){
                intervals[++m] = {polls[i].first, 0};
            } else {
                intervals[m].second = polls[i].first - 1;
                intervals[++m] = {polls[i].first, 0};
            }
        } else if(polls[i].second == 1) {
            if(polls[i].first < intervals[m].first)
                m--;
            intervals[m].second = polls[i].first;
            if(open > 0) {
                intervals[++m] = {polls[i].first + 1, 0}; /// grija cu +1, dar oricum astea care incep sunt primeel
            }
        }
    }
    for(i = 1; i <= m; i++) {
        dp[0][i] = 1;
//        debugs(intervals[i].first);
//        debug(intervals[i].second);
    }
    dp[0][0] = 1;
    ll maxi = 0;
    for(i = 1; i <= n; i++) {
        for(ll k = 1; k <= m; k++) {
            ll lung = intervals[k].second - intervals[k].first + 1;
            dp[i][k] = dp[i][k - 1]; /// nu facem nimic cu k-ul asta
            if(dp[i][k] >= MOD)
                dp[i][k] -= MOD;
            ll sum = 0;
            for(ll j = i; j >= 1; j--) {
                if((i - j + 1 <= lung) && (v[j].first <= intervals[k].first && intervals[k].second <= v[j].second)) {
                    /// o secventa continuea j .. i  va llra aici, nu punem break ca sa luam si variantele cand unele lipsesc
                    ll cnt = (i - j + 1);
                    sum += comb(lung, cnt);
                    maxi = max(maxi, lung);
                    sum %= MOD;
                }
                dp[i][k] += (dp[j - 1][k - 1] * sum) % MOD;
                if(dp[i][k] >= MOD)
                    dp[i][k] -= MOD;
            }
        }
    }
    ll sol = 0;
    for(i =  1; i <= n; i++) {
        sol += dp[i][m];
        sol %= MOD;
    }
    cout << sol;
    return 0;
}

Compilation message

boat.cpp: In function 'int main()':
boat.cpp:76:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |     for(i = 0; i < polls.size(); i++) {
      |                ~~^~~~~~~~~~~~~~
boat.cpp:67:14: warning: unused variable 'j' [-Wunused-variable]
   67 |     ll n, i, j;
      |              ^

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 265 ms 4284 KB Output is correct
2 Correct 241 ms 4300 KB Output is correct
3 Correct 257 ms 4228 KB Output is correct
4 Correct 246 ms 4300 KB Output is correct
5 Correct 262 ms 4404 KB Output is correct
6 Correct 248 ms 4328 KB Output is correct
7 Correct 278 ms 4300 KB Output is correct
8 Correct 265 ms 4300 KB Output is correct
9 Correct 238 ms 4256 KB Output is correct
10 Correct 243 ms 4216 KB Output is correct
11 Correct 274 ms 4264 KB Output is correct
12 Correct 240 ms 4332 KB Output is correct
13 Correct 269 ms 4212 KB Output is correct
14 Correct 250 ms 4256 KB Output is correct
15 Correct 241 ms 4216 KB Output is correct
16 Correct 50 ms 2596 KB Output is correct
17 Correct 54 ms 2636 KB Output is correct
18 Correct 44 ms 2724 KB Output is correct
19 Correct 47 ms 2720 KB Output is correct
20 Correct 50 ms 2640 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 265 ms 4284 KB Output is correct
2 Correct 241 ms 4300 KB Output is correct
3 Correct 257 ms 4228 KB Output is correct
4 Correct 246 ms 4300 KB Output is correct
5 Correct 262 ms 4404 KB Output is correct
6 Correct 248 ms 4328 KB Output is correct
7 Correct 278 ms 4300 KB Output is correct
8 Correct 265 ms 4300 KB Output is correct
9 Correct 238 ms 4256 KB Output is correct
10 Correct 243 ms 4216 KB Output is correct
11 Correct 274 ms 4264 KB Output is correct
12 Correct 240 ms 4332 KB Output is correct
13 Correct 269 ms 4212 KB Output is correct
14 Correct 250 ms 4256 KB Output is correct
15 Correct 241 ms 4216 KB Output is correct
16 Correct 50 ms 2596 KB Output is correct
17 Correct 54 ms 2636 KB Output is correct
18 Correct 44 ms 2724 KB Output is correct
19 Correct 47 ms 2720 KB Output is correct
20 Correct 50 ms 2640 KB Output is correct
21 Incorrect 753 ms 5988 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2073 ms 460 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 265 ms 4284 KB Output is correct
2 Correct 241 ms 4300 KB Output is correct
3 Correct 257 ms 4228 KB Output is correct
4 Correct 246 ms 4300 KB Output is correct
5 Correct 262 ms 4404 KB Output is correct
6 Correct 248 ms 4328 KB Output is correct
7 Correct 278 ms 4300 KB Output is correct
8 Correct 265 ms 4300 KB Output is correct
9 Correct 238 ms 4256 KB Output is correct
10 Correct 243 ms 4216 KB Output is correct
11 Correct 274 ms 4264 KB Output is correct
12 Correct 240 ms 4332 KB Output is correct
13 Correct 269 ms 4212 KB Output is correct
14 Correct 250 ms 4256 KB Output is correct
15 Correct 241 ms 4216 KB Output is correct
16 Correct 50 ms 2596 KB Output is correct
17 Correct 54 ms 2636 KB Output is correct
18 Correct 44 ms 2724 KB Output is correct
19 Correct 47 ms 2720 KB Output is correct
20 Correct 50 ms 2640 KB Output is correct
21 Incorrect 753 ms 5988 KB Output isn't correct
22 Halted 0 ms 0 KB -