Codeforces Round 771 (Div. 2)

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
1638 Codeforces Round 771 (Div. 2) FINISHED False 7200 92417063 Feb. 14, 2022, 2:35 p.m.

Problems

Solved$
Index
Name
Type
Tags
Community Tag
Rating
( 14901 ) C Inversion Graph PROGRAMMING ds graphs math

B'You are given a permutation p_1, p_2, ... , p_n . Then, an undirected graph is constructed in the following way: add an edge between vertices i , j such that i < j if and only if p_i > p_j . Your task is to count the number of connected components in this graph. Two vertices u and v belong to the same connected component if and only if there is at least one path along edges connecting u and v . A permutation is an array consisting of n distinct integers from 1 to n in arbitrary order. For example, [2,3,1,5,4] is a permutation, but [1,2,2] is not a permutation ( 2 appears twice in the array) and [1,3,4] is also not a permutation ( n=3 but there is 4 in the array). Each test contains multiple test cases. The first line contains a single integer t ( 1 <= t <= 10^5 ) -- the number of test cases. Description of the test cases follows. The first line of each test case contains a single integer n ( 1 <= n <= 10^5 ) -- the length of the permutation. The second line of each test case contains n integers p_1, p_2, ... , p_n ( 1 <= p_i <= n ) -- the elements of the permutation. It is guaranteed that the sum of n over all test cases does not exceed 2 cdot 10^5 . For each test case, print one integer k -- the number of connected components. Each separate test case is depicted in the image below. The colored squares represent the elements of the permutation. For one permutation, each color represents some connected component. The number of distinct colors is the answer. '...

Tutorials

Codeforces Round #771 Editorial

Submissions

Submission Id
Author(s)
Index
Submitted
Verdict
Language
Test Set
Tests Passed
Time taken (ms)
Memory Consumed (bytes)
Tags
Rating
146422927 ruban C Feb. 14, 2022, 4:21 p.m. OK FPC TESTS 55 280 94003200
146449596 xoyoon2 C Feb. 14, 2022, 7:49 p.m. OK GNU C11 TESTS 55 374 1433600
146455518 ztfgsxdgyt C Feb. 14, 2022, 9:28 p.m. OK GNU C11 TESTS 55 374 1536000
146447697 rainweep C Feb. 14, 2022, 7:28 p.m. OK GNU C11 TESTS 55 390 409600
146465036 1435730 C Feb. 15, 2022, 2:26 a.m. OK GNU C11 TESTS 55 421 1228800
146455845 _joKer_0 C Feb. 14, 2022, 9:35 p.m. OK GNU C++14 TESTS 55 46 0
146453000 heba.daraghmeh C Feb. 14, 2022, 8:39 p.m. OK GNU C++14 TESTS 55 46 0
146445757 durjoy122 C Feb. 14, 2022, 7:13 p.m. OK GNU C++14 TESTS 55 46 0
146419525 naeby C Feb. 14, 2022, 4:12 p.m. OK GNU C++14 TESTS 55 46 0
146455906 _joKer_0 C Feb. 14, 2022, 9:37 p.m. OK GNU C++14 TESTS 55 46 0
146479484 AAZ_01 C Feb. 15, 2022, 6 a.m. OK GNU C++14 TESTS 55 46 0
146455875 _joKer_0 C Feb. 14, 2022, 9:36 p.m. OK GNU C++14 TESTS 55 46 0
146426273 ClassicMJ_9414 C Feb. 14, 2022, 4:30 p.m. OK GNU C++14 TESTS 55 46 409600
146469838 Fish_Song C Feb. 15, 2022, 3:51 a.m. OK GNU C++14 TESTS 55 46 409600
146472374 Shirokun C Feb. 15, 2022, 4:29 a.m. OK GNU C++14 TESTS 55 46 409600
146476794 onteeae C Feb. 15, 2022, 5:29 a.m. OK GNU C++17 TESTS 55 15 2969600
146467657 hotwords C Feb. 15, 2022, 3:17 a.m. OK GNU C++17 TESTS 55 46 0
146465595 lyc_China C Feb. 15, 2022, 2:38 a.m. OK GNU C++17 TESTS 55 46 0
146465289 fuadul C Feb. 15, 2022, 2:31 a.m. OK GNU C++17 TESTS 55 46 0
146459651 abotaha23 C Feb. 14, 2022, 11:53 p.m. OK GNU C++17 TESTS 55 46 0
146478548 omar_f C Feb. 15, 2022, 5:49 a.m. OK GNU C++17 TESTS 55 46 0
146450150 rahulmallick1115 C Feb. 14, 2022, 7:56 p.m. OK GNU C++17 TESTS 55 46 0
146473670 soccoder C Feb. 15, 2022, 4:47 a.m. OK GNU C++17 TESTS 55 46 0
146470162 Anchord C Feb. 15, 2022, 3:56 a.m. OK GNU C++17 TESTS 55 46 0
146469880 RFSS_ C Feb. 15, 2022, 3:52 a.m. OK GNU C++17 TESTS 55 46 0
146462368 binminh01 C Feb. 15, 2022, 1:24 a.m. OK GNU C++17 (64) TESTS 55 31 0
146465824 pranay.2 C Feb. 15, 2022, 2:42 a.m. OK GNU C++17 (64) TESTS 55 31 0
146445852 panyaoyu1999 C Feb. 14, 2022, 7:13 p.m. OK GNU C++17 (64) TESTS 55 31 409600
146464322 InariInDream C Feb. 15, 2022, 2:12 a.m. OK GNU C++17 (64) TESTS 55 31 409600
146461711 tsaqifAdot C Feb. 15, 2022, 1:06 a.m. OK GNU C++17 (64) TESTS 55 31 819200
146469767 _Neel_ C Feb. 15, 2022, 3:51 a.m. OK GNU C++17 (64) TESTS 55 31 819200
146465048 EotUL8d7 C Feb. 15, 2022, 2:26 a.m. OK GNU C++17 (64) TESTS 55 31 819200
146446869 alever C Feb. 14, 2022, 7:20 p.m. OK GNU C++17 (64) TESTS 55 31 819200
146446324 timg_ C Feb. 14, 2022, 7:16 p.m. OK GNU C++17 (64) TESTS 55 31 819200
146465482 linxd C Feb. 15, 2022, 2:35 a.m. OK GNU C++17 (64) TESTS 55 31 1024000
146460438 ElectroMaster3 C Feb. 15, 2022, 12:22 a.m. OK GNU C++20 (64) TESTS 55 31 0
146450360 nesco C Feb. 14, 2022, 7:58 p.m. OK GNU C++20 (64) TESTS 55 31 0
146447707 dush1729 C Feb. 14, 2022, 7:28 p.m. OK GNU C++20 (64) TESTS 55 31 0
146446081 ultimate_pal C Feb. 14, 2022, 7:15 p.m. OK GNU C++20 (64) TESTS 55 31 0
146422664 sarwar__ C Feb. 14, 2022, 4:21 p.m. OK GNU C++20 (64) TESTS 55 31 0
146462864 blue_suno C Feb. 15, 2022, 1:37 a.m. OK GNU C++20 (64) TESTS 55 31 0
146470167 starmind C Feb. 15, 2022, 3:56 a.m. OK GNU C++20 (64) TESTS 55 31 0
146474413 Mr_Skills C Feb. 15, 2022, 4:57 a.m. OK GNU C++20 (64) TESTS 55 31 0
146461202 Porag_2742 C Feb. 15, 2022, 12:49 a.m. OK GNU C++20 (64) TESTS 55 31 0
146451464 _ForeRunner_ C Feb. 14, 2022, 8:14 p.m. OK GNU C++20 (64) TESTS 55 31 307200
146459739 0x3F C Feb. 14, 2022, 11:57 p.m. OK Go TESTS 55 109 1024000
146459609 0x3F C Feb. 14, 2022, 11:51 p.m. OK Go TESTS 55 109 2764800
146460580 koqo C Feb. 15, 2022, 12:28 a.m. OK Go TESTS 55 124 4096000
146464999 meooow C Feb. 15, 2022, 2:26 a.m. OK Haskell TESTS 55 93 2150400
146451175 jyoti360 C Feb. 14, 2022, 8:10 p.m. OK Java 11 TESTS 55 171 0
146468043 sauravmandal C Feb. 15, 2022, 3:24 a.m. OK Java 11 TESTS 55 202 0
146449321 Satyaa C Feb. 14, 2022, 7:45 p.m. OK Java 11 TESTS 55 202 0
146447619 sohamdas301 C Feb. 14, 2022, 7:27 p.m. OK Java 11 TESTS 55 202 0
146426225 sagar197 C Feb. 14, 2022, 4:30 p.m. OK Java 11 TESTS 55 202 0
146425771 Sandy_coder2001 C Feb. 14, 2022, 4:29 p.m. OK Java 11 TESTS 55 202 0
146421156 karunapal_chava C Feb. 14, 2022, 4:17 p.m. OK Java 11 TESTS 55 218 0
146461177 the_unseen C Feb. 15, 2022, 12:48 a.m. OK Java 11 TESTS 55 218 0
146470813 kalzor C Feb. 15, 2022, 4:06 a.m. OK Java 11 TESTS 55 233 0
146446372 ujjwalll C Feb. 14, 2022, 7:16 p.m. OK Java 11 TESTS 55 233 0
146450977 arutsudar C Feb. 14, 2022, 8:07 p.m. OK Java 8 TESTS 55 140 0
146446938 chinmaya21 C Feb. 14, 2022, 7:21 p.m. OK Java 8 TESTS 55 140 0
146451021 arutsudar C Feb. 14, 2022, 8:08 p.m. OK Java 8 TESTS 55 155 102400
146468254 aggarwalanshul01 C Feb. 15, 2022, 3:28 a.m. OK Java 8 TESTS 55 171 1536000
146464331 lcheeme1 C Feb. 15, 2022, 2:12 a.m. OK Java 8 TESTS 55 202 6041600
146423683 sanjayram21 C Feb. 14, 2022, 4:24 p.m. OK Java 8 TESTS 55 234 2457600
146449807 Omar_Mohammad C Feb. 14, 2022, 7:51 p.m. OK Java 8 TESTS 55 249 1536000
146421761 khwrzm C Feb. 14, 2022, 4:18 p.m. OK Java 8 TESTS 55 280 72396800
146471980 athu18 C Feb. 15, 2022, 4:23 a.m. OK Java 8 TESTS 55 311 0
146452155 harshitnsharma C Feb. 14, 2022, 8:25 p.m. OK Java 8 TESTS 55 326 0
146469910 starmind C Feb. 15, 2022, 3:52 a.m. OK MS C++ 2017 TESTS 55 140 0
146468088 starmind C Feb. 15, 2022, 3:25 a.m. OK MS C++ 2017 TESTS 55 156 1024000
146467211 starmind C Feb. 15, 2022, 3:09 a.m. OK MS C++ 2017 TESTS 55 156 1945600
146453569 abdelrahman_rashed C Feb. 14, 2022, 8:50 p.m. OK MS C++ 2017 TESTS 55 202 3788800
146473746 Ir0nic_Joker C Feb. 15, 2022, 4:48 a.m. OK MS C++ 2017 TESTS 55 452 409600
146445914 misaka12435 C Feb. 14, 2022, 7:14 p.m. OK MS C++ 2017 TESTS 55 452 819200
146424762 WUT_ZJL C Feb. 14, 2022, 4:26 p.m. OK MS C++ 2017 TESTS 55 452 819200
146463530 Fy9091 C Feb. 15, 2022, 1:54 a.m. OK MS C++ 2017 TESTS 55 483 819200
146468198 capability_Wu C Feb. 15, 2022, 3:27 a.m. OK MS C++ 2017 TESTS 55 498 819200
146423511 JYJgogogo C Feb. 14, 2022, 4:23 p.m. OK MS C++ 2017 TESTS 55 764 409600
146445246 1_2_3_4_5_9 C Feb. 14, 2022, 7:11 p.m. OK PyPy 2 TESTS 55 155 11878400
146477480 feelme C Feb. 15, 2022, 5:37 a.m. OK PyPy 3 TESTS 55 155 12185600
146427530 mnkqc C Feb. 14, 2022, 4:33 p.m. OK PyPy 3 TESTS 55 155 12595200
146456682 hritik3878 C Feb. 14, 2022, 9:57 p.m. OK PyPy 3 TESTS 55 155 14028800
146425631 Mr._Oogway C Feb. 14, 2022, 4:29 p.m. OK PyPy 3 TESTS 55 171 13107200
146474266 ultimate_pal C Feb. 15, 2022, 4:55 a.m. OK PyPy 3 TESTS 55 202 12697600
146457961 Ahmed_Turkman C Feb. 14, 2022, 10:34 p.m. OK PyPy 3 TESTS 55 217 13312000
146454477 akshitm16 C Feb. 14, 2022, 9:07 p.m. OK PyPy 3 TESTS 55 218 12595200
146447271 KeiTsukishima C Feb. 14, 2022, 7:24 p.m. OK PyPy 3 TESTS 55 218 15462400
146424564 Chiho C Feb. 14, 2022, 4:26 p.m. OK PyPy 3 TESTS 55 233 12697600
146460687 majay1638 C Feb. 15, 2022, 12:31 a.m. OK PyPy 3 TESTS 55 233 13312000
146478079 mayank35 C Feb. 15, 2022, 5:44 a.m. OK PyPy 3-64 TESTS 55 171 18534400
146459082 raushnn C Feb. 14, 2022, 11:30 p.m. OK PyPy 3-64 TESTS 55 171 20992000
146475510 sakshatmali C Feb. 15, 2022, 5:12 a.m. OK PyPy 3-64 TESTS 55 186 18636800
146458437 bpdolson C Feb. 14, 2022, 10:51 p.m. OK PyPy 3-64 TESTS 55 202 22016000
146423617 NKUCristiano C Feb. 14, 2022, 4:23 p.m. OK PyPy 3-64 TESTS 55 217 24678400
146470470 Youarenotgood C Feb. 15, 2022, 4:01 a.m. OK PyPy 3-64 TESTS 55 233 16281600
146463375 sjNxksbzj C Feb. 15, 2022, 1:50 a.m. OK PyPy 3-64 TESTS 55 233 17817600
146473830 Himanshu_Kaithal C Feb. 15, 2022, 4:49 a.m. OK PyPy 3-64 TESTS 55 233 18124800
146424582 StillMortal C Feb. 14, 2022, 4:26 p.m. OK PyPy 3-64 TESTS 55 233 18432000
146424510 Rajveer_100 C Feb. 14, 2022, 4:26 p.m. OK PyPy 3-64 TESTS 55 233 18841600
146445335 OLOGY C Feb. 14, 2022, 7:11 p.m. OK Python 2 TESTS 55 265 7475200
146471656 Marshmello C Feb. 15, 2022, 4:19 a.m. OK Python 2 TESTS 55 717 12902400
146423232 Skillful_Wanderer C Feb. 14, 2022, 4:22 p.m. OK Python 3 TESTS 55 327 9420800
146448526 r57shell C Feb. 14, 2022, 7:36 p.m. OK Python 3 TESTS 55 342 7680000
146471904 pennymagic156 C Feb. 15, 2022, 4:22 a.m. OK Python 3 TESTS 55 343 9420800
146469427 Dahoas C Feb. 15, 2022, 3:46 a.m. OK Python 3 TESTS 55 373 7782400
146447476 xoyoon2 C Feb. 14, 2022, 7:26 p.m. OK Python 3 TESTS 55 389 9420800
146446455 xoyoon2 C Feb. 14, 2022, 7:17 p.m. OK Python 3 TESTS 55 405 9420800
146472309 pennymagic156 C Feb. 15, 2022, 4:28 a.m. OK Python 3 TESTS 55 420 9420800
146474442 shehebe C Feb. 15, 2022, 4:58 a.m. OK Python 3 TESTS 55 436 12288000
146469639 pennymagic156 C Feb. 15, 2022, 3:49 a.m. OK Python 3 TESTS 55 468 14438400
146447120 KeiTsukishima C Feb. 14, 2022, 7:22 p.m. OK Python 3 TESTS 55 499 10035200

remove filters

Back to search problems