Polynomial Round 2022 (Div. 1 + Div. 2, Rated, Prizes!)

Solutions are presented as using the least memory and the fastest execution time. It also takes the top 10 most recent solutions from each language. If you want to limit to a specific index, click the "Solved" button and go to that problem.

ContestId
Name
Phase
Frozen
Duration (Seconds)
Relative Time
Start Time
1774 Polynomial Round 2022 (Div. 1 + Div. 2, Rated, Prizes!) FINISHED False 9000 65892263 Dec. 17, 2022, 2:35 p.m.

Problems

Solved$
Index
Name
Type
Tags
Community Tag
Rating
( 450 ) G Segment Covering PROGRAMMING brute force combinatorics constructive algorithms data structures trees

B"ChthollyNotaSeniorious gives DataStructures a number axis with m distinct segments on it. Let f(l,r) be the number of ways to choose an even number of segments such that the union of them is exactly [l,r] , and g(l,r) be the number of ways to choose an odd number of segments such that the union of them is exactly [l,r] . ChthollyNotaSeniorious asked DataStructures q questions. In each query, ChthollyNotaSeniorious will give DataStructures two numbers l, r , and now he wishes that you can help him find the value f(l,r)-g(l,r) modulo 998 ,244 ,353 so that he wouldn't let her down. The first line of input contains two integers m ( 1 <= q m <= q 2 cdot 10^5 ) and q ( 1 <= q q <= q 2 cdot 10^5 ) -- the number of segments and queries, correspondingly. The i -th of the next m lines contains two integers x_i and y_i ( 1 <= q x_i < y_i <= q 10^9 ), denoting a segment [x_i, y_i] . It is guaranteed that all segments are distinct. More formally, there do not exist two numbers i, j with 1 <= i < j <= m such that x_i = x_j and y_i = y_j . The i -th of the next q lines contains two integers l_i and r_i ( 1 <= q l_i < r_i <= q 10^9 ), describing a query. For each query, output a single integer -- f(l_i,r_i)-g(l_i,r_i) modulo 998 ,244 ,353 . In the first query, we have to find f(1, 4) - g(1, 4) . The only subset of segments with union [1, 4] is {[1, 3], [2, 4] } , so f(1, 4) = 1, g(1, 4) = 0 . In the second query, we have to find f(1, 5) - g(1, 5) . The only subsets of segments with union [1, 5] are {[1, 3], [2, 4], [3, 5] } and {[1, 3], [3, 5] } , so f(1, 5) = 1, g(1, 5) = 1 . "...

Tutorials

Polynomial Round 2022 (Div. 1 + Div. 2) Editorial

Submissions

Submission Id
Author(s)
Index
Submitted
Verdict
Language
Test Set
Tests Passed
Time taken (ms)
Memory Consumed (bytes)
Tags
Rating
185717001 rainboy G Dec. 17, 2022, 6:35 p.m. OK GNU C11 TESTS 26 1638 17612800
185741703 hank55663 G Dec. 18, 2022, 2:46 a.m. OK GNU C++14 TESTS 26 842 29593600
185743998 ZCKevin G Dec. 18, 2022, 3:42 a.m. OK GNU C++17 TESTS 26 420 29593600
185707593 ZCKevin G Dec. 17, 2022, 4:59 p.m. OK GNU C++17 TESTS 26 421 29593600
185702434 ugly2333 G Dec. 17, 2022, 4:45 p.m. OK GNU C++17 TESTS 26 483 24064000
185727507 Ant_Man G Dec. 17, 2022, 8:27 p.m. OK GNU C++17 TESTS 26 561 20684800
185729638 omar_ayman_21 G Dec. 17, 2022, 8:58 p.m. OK GNU C++17 TESTS 26 561 20684800
185740837 SegT1018 G Dec. 18, 2022, 2:24 a.m. OK GNU C++17 TESTS 26 701 49868800
185741032 nick1004 G Dec. 18, 2022, 2:29 a.m. OK GNU C++17 TESTS 26 748 49868800
185706872 slime G Dec. 17, 2022, 4:57 p.m. OK GNU C++17 TESTS 26 1435 243609600
185701804 LJC00118 G Dec. 17, 2022, 4:43 p.m. OK GNU C++17 (64) TESTS 26 530 38502400
185732261 mhq G Dec. 17, 2022, 9:47 p.m. OK GNU C++17 (64) TESTS 26 561 118784000
185721733 Benq G Dec. 17, 2022, 7:17 p.m. OK GNU C++17 (64) TESTS 26 623 18022400
185742284 Mr_Eight G Dec. 18, 2022, 3:01 a.m. OK GNU C++17 (64) TESTS 26 733 112230400
185708682 SSRS_ G Dec. 17, 2022, 5:01 p.m. OK GNU C++17 (64) TESTS 26 951 25702400
185717851 ainta G Dec. 17, 2022, 6:42 p.m. OK GNU C++17 (64) TESTS 26 1029 31744000
185700930 ksun48 G Dec. 17, 2022, 4:40 p.m. OK GNU C++20 (64) TESTS 26 265 27750400
185710209 ecnerwala G Dec. 17, 2022, 5:04 p.m. OK GNU C++20 (64) TESTS 26 483 19353600
185746206 njwrz G Dec. 18, 2022, 4:29 a.m. OK GNU C++20 (64) TESTS 26 545 21708800
185719954 BurnedChicken G Dec. 17, 2022, 6:59 p.m. OK GNU C++20 (64) TESTS 26 639 47104000
185709786 tourist G Dec. 17, 2022, 5:03 p.m. OK GNU C++20 (64) TESTS 26 685 29491200
185704068 inaFSTream G Dec. 17, 2022, 4:49 p.m. OK GNU C++20 (64) TESTS 26 1201 82329600
185740223 Bugman G Dec. 18, 2022, 2:08 a.m. OK GNU C++20 (64) TESTS 26 1248 145715200
185739701 Bugman G Dec. 18, 2022, 1:53 a.m. OK GNU C++20 (64) TESTS 26 1263 145715200
185739267 Bugman G Dec. 18, 2022, 1:41 a.m. OK GNU C++20 (64) TESTS 26 1450 148992000

remove filters

Back to search problems