codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1260.md (8781B)


      1 Source: https://codeforces.com/blog/entry/71805
      2 
      3 [1260A - Heating](/contest/1260/problem/A "Educational Codeforces Round 77 (Rated for Div. 2)")
      4 
      5 Idea: [adedalic](/profile/adedalic "International Master adedalic")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (adedalic)**
     12 
     13 ```
     14 #include<bits/stdc++.h>
     15 using namespace std;
     16 
     17 int c, sum;
     18 
     19 inline bool read() {
     20 	if(!(cin >> c >> sum))
     21 		return false;
     22 	return true;
     23 }
     24 
     25 inline void solve() {
     26 	int d = sum / c;
     27 	int rem = sum % c;
     28 	cout << rem * (d + 1) * (d + 1) + (c - rem) * d * d << endl;
     29 }
     30 
     31 int main() {
     32 #ifdef _DEBUG
     33 	freopen("input.txt", "r", stdin);
     34 #endif
     35 	int n; cin >> n;
     36 	while(n--) {
     37 		read();
     38 		solve();
     39 	}
     40 	return 0;
     41 }
     42 ```
     43 
     44 [1260B - Obtain Two Zeroes](/contest/1260/problem/B "Educational Codeforces Round 77 (Rated for Div. 2)")
     45 
     46 Idea: [Roms](/profile/Roms "Master Roms")
     47 
     48 **Tutorial**
     49 
     50 Tutorial is loading...
     51 
     52 **Solution (Roms)**
     53 
     54 ```
     55 for t in range(int(input())):
     56 	a, b = map(int, input().split())
     57 	if a > b:
     58 		a, b = b, a
     59 	print ('YES' if ( ((a + b) % 3) == 0 and a * 2 >= b) else 'NO')
     60 ```
     61 
     62 [1260C - Infinite Fence](/contest/1260/problem/C "Educational Codeforces Round 77 (Rated for Div. 2)")
     63 
     64 Idea: [adedalic](/profile/adedalic "International Master adedalic")
     65 
     66 **Tutorial**
     67 
     68 Tutorial is loading...
     69 
     70 **Solution (adedalic)**
     71 
     72 ```
     73 #include<bits/stdc++.h>
     74 using namespace std;
     75 typedef long long li;
     76 
     77 li a, b, k;
     78 
     79 inline bool read() {
     80 	if(!(cin >> a >> b >> k))
     81 		return false;
     82 	return true;
     83 }
     84 
     85 inline void solve() {
     86 	li g = __gcd(a, b);
     87 	a /= g;
     88 	b /= g;
     89 	if(a > b)
     90 		swap(a, b);
     91 	if((k - 1) * a + 1 < b)
     92 		cout << "REBEL";
     93 	else
     94 		cout << "OBEY";
     95 	cout << endl;
     96 }
     97 
     98 int main() {
     99 #ifdef _DEBUG
    100 	freopen("input.txt", "r", stdin);
    101 #endif
    102 	int tc; cin >> tc;
    103 	while(tc--) {
    104 		read();
    105 		solve();
    106 	}
    107 	return 0;
    108 }
    109 ```
    110 
    111 [1260D - A Game with Traps](/contest/1260/problem/D "Educational Codeforces Round 77 (Rated for Div. 2)")
    112 
    113 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    114 
    115 **Tutorial**
    116 
    117 Tutorial is loading...
    118 
    119 **Solution (BledDest)**
    120 
    121 ```
    122 #define _CRT_SECURE_NO_WARNINGS
    123 
    124 #include<iostream>
    125 #include<cstdio>
    126 #include<vector>
    127 #include<algorithm>
    128 #include<map>
    129 
    130 using namespace std;
    131 
    132 typedef pair<int, int> pt;
    133 
    134 #define x first
    135 #define y second
    136 
    137 int m, n, k, t;
    138 vector<int> l, r, d, a;
    139 
    140 bool can(int x)
    141 {
    142 	int mn = int(1e9);
    143 	for (int i = 0; i < x; i++)
    144 		mn = min(mn, a[i]);
    145 	vector<pt> segm;
    146 	for (int i = 0; i < k; i++)
    147 		if (d[i] > mn)
    148 			segm.push_back(make_pair(l[i], r[i]));
    149 	int req_time = 0;
    150 	sort(segm.begin(), segm.end());
    151 	int lastr = 0;
    152 	for (auto s : segm)
    153 	{
    154 		if (s.x <= lastr)
    155 		{
    156 			req_time += max(0, s.y - lastr);
    157 			lastr = max(s.y, lastr);
    158 		}
    159 		else
    160 		{
    161 			req_time += s.y - s.x + 1;
    162 			lastr = s.y;
    163 		}
    164 	}
    165 	req_time = 2 * req_time + n + 1;
    166 	return req_time <= t;
    167 }
    168 
    169 int main()
    170 {
    171 #ifdef _DEBUG
    172 	freopen("input.txt", "r", stdin);
    173 	freopen("output.txt", "w", stdout);
    174 #endif
    175 	scanf("%d %d %d %d", &m, &n, &k, &t);
    176 	a.resize(m);
    177 	for (int i = 0; i < m; i++)
    178 		scanf("%d", &a[i]);
    179 	sort(a.begin(), a.end());
    180 	reverse(a.begin(), a.end());
    181 	l.resize(k);
    182 	r.resize(k);
    183 	d.resize(k);
    184 	for (int i = 0; i < k; i++)
    185 		scanf("%d %d %d", &l[i], &r[i], &d[i]);
    186 
    187 	int lf = 0;
    188 	int rg = m + 1;
    189 	while (rg - lf > 1)
    190 	{
    191 		int mid = (lf + rg) / 2;
    192 		if (can(mid))
    193 			lf = mid;
    194 		else
    195 			rg = mid;
    196 	}
    197 	printf("%d\n", lf);
    198 	return 0;
    199 }
    200 ```
    201 
    202 [1260E - Tournament](/contest/1260/problem/E "Educational Codeforces Round 77 (Rated for Div. 2)")
    203 
    204 Idea: [Roms](/profile/Roms "Master Roms")
    205 
    206 **Tutorial**
    207 
    208 Tutorial is loading...
    209 
    210 **Solution (Roms)**
    211 
    212 ```
    213 #include <bits/stdc++.h>
    214 
    215 using namespace std;
    216 
    217 const int LOGN = 20;
    218 const int N = (1 << LOGN) + 99;
    219 const long long INF = 1e18;
    220 
    221 int n;
    222 int a[N];
    223 long long dp[LOGN+2][N];
    224 int sum[100];
    225 
    226 long long calc(int cnt, int pos){
    227 	long long &res = dp[cnt][pos];
    228 	if(res != -1) return res;
    229 
    230 	if(a[pos] == -1) return res = 0;
    231 	int rem = sum[cnt] - pos;
    232 
    233 	res = INF;
    234 	if(cnt < LOGN)
    235 		res = calc(cnt + 1, pos + 1) + a[pos];
    236 	if(rem > 0)		
    237 		res = min(res, calc(cnt, pos + 1));
    238 
    239 	return res;
    240 }
    241 
    242 int main() {	
    243 	scanf("%d", &n);
    244 	for(int i = 0; i < n; ++i)
    245 		scanf("%d", a + i);
    246 
    247 	for(int i = 1, x = n / 2; i < 100; ++i, x /= 2)
    248 		sum[i] = sum[i - 1] + x;
    249 	
    250 	reverse(a, a + n);
    251 	memset(dp, -1, sizeof dp);
    252 	printf("%lld", calc(0, 0));	
    253 	return 0;
    254 }                             	
    255 ```
    256 
    257 [1260F - Colored Tree](/contest/1260/problem/F "Educational Codeforces Round 77 (Rated for Div. 2)")
    258 
    259 Idea: [RDDCCD](/profile/RDDCCD "Master RDDCCD")
    260 
    261 **Tutorial**
    262 
    263 Tutorial is loading...
    264 
    265 **Solution (RDDCCD)**
    266 
    267 ```
    268 #include<bits/stdc++.h>
    269 using namespace std;
    270 int n ;
    271 const int maxn = 1e5 + 5;
    272 const int mod = 1e9 + 7 ;
    273 vector<int> E[maxn];
    274 vector<int> in[maxn] , out[maxn];
    275 int cm = 0;
    276 int l[maxn] , dfn = 0 , dep[maxn];
    277 int g[maxn];
    278 int siz[maxn] , top[maxn] , h[maxn] , f[maxn];
    279 ///-----segment tree
    280 struct seg
    281 {
    282     int l , r;
    283     int sum , add ;
    284 }Node[maxn * 4];
    285 
    286 void build(int u,int l,int r)
    287 {
    288     Node[u].l = l , Node[u].r = r;
    289     Node[u].sum = Node[u].add = 0;
    290     if(l == r) return ;
    291     build(u<<1 , l , (l + r >> 1));
    292     build(u<<1|1 , (l + r >>1) + 1 , r);
    293     return ;
    294 }
    295 void pd(int u)
    296 {
    297     Node[u].sum = (1LL*Node[u].add*(Node[u].r - Node[u].l + 1) + Node[u].sum) % mod ;
    298     if(Node[u].l == Node[u].r) {
    299         Node[u].add = 0 ;return ;
    300     }
    301     (Node[u<<1].add += Node[u].add ) %= mod;
    302     (Node[u<<1|1].add += Node[u].add ) %= mod;
    303     Node[u].add = 0 ; return ;
    304 }
    305 void modify(int u,int l,int r,int v)
    306 {
    307     if(Node[u].l == l && Node[u].r == r) {
    308         (Node[u].add += v ) %= mod;
    309         pd(u) ; return ;
    310         return ;
    311     }
    312     pd(u) ;
    313     if(Node[u<<1].r >= r) {modify(u<<1 , l , r , v) ; pd(u<<1|1);}
    314     else if(Node[u<<1|1].l <= l) {modify(u<<1|1 , l , r , v) ; pd(u<<1) ;}
    315     else {
    316         modify(u<<1 , l , Node[u<<1].r , v) ;
    317         modify(u<<1|1 , Node[u<<1|1].l , r , v);
    318     }
    319     Node[u].sum = (Node[u<<1].sum + Node[u<<1|1].sum) % mod;
    320     return ;
    321 }
    322 int query(int u,int l,int r)
    323 {
    324     pd(u) ;
    325     if(Node[u].l == l && Node[u].r == r) return Node[u].sum ;
    326     if(Node[u<<1].r >= r) return query(u<<1 , l , r) ;
    327     else if(Node[u<<1|1].l <= l) return query(u<<1|1 , l , r);
    328     else return (query(u<<1 , l , Node[u<<1].r) + query(u<<1|1 , Node[u<<1|1].l , r)) % mod;
    329 }
    330 ///---segment tree end
    331 void dfs(int fa,int u,int d)
    332 {
    333     f[u] = fa;
    334     dep[u] = d;siz[u] = 1;h[u] = -1;
    335     for(int i = 0;i < E[u].size();i++) {
    336         if(E[u][i] != fa) {
    337             dfs(u , E[u][i] , d + 1) ;siz[u] += siz[E[u][i]];
    338             if(h[u] == -1 || siz[E[u][i]] > siz[E[u][h[u]]]) h[u] = i;
    339         }
    340     }
    341     return ;
    342 }
    343 void dfs2(int fa,int u)
    344 {
    345     l[u] = ++dfn;
    346     if(h[u] != -1) {
    347         top[E[u][h[u]]] = top[u] ;
    348         dfs2(u , E[u][h[u]]);
    349     }
    350     for(int i = 0;i < E[u].size();i++) {
    351         if(E[u][i] != fa && i != h[u]) {
    352             top[E[u][i]] = E[u][i] ;
    353             dfs2(u , E[u][i]) ;
    354         }
    355     }
    356     return ;
    357 }
    358 int fpow(int a,int b)
    359 {
    360     int ans = 1;
    361     while(b) {
    362         if(b & 1) ans = (1LL * ans * a) % mod;
    363         a = (1LL * a * a) % mod ;b >>= 1;
    364     }
    365     return ans;
    366 }
    367 void add(int u,int v)
    368 {
    369     while(u) {
    370         modify(1 , l[top[u]] , l[u] , v) ;
    371         u = f[top[u]] ;
    372     }
    373     return ;
    374 }
    375 int cal(int u)
    376 {
    377     int ans = mod - query(1 , 1 , 1);
    378     while(u) {
    379         ans = (ans + query(1 , l[top[u]] , l[u])) % mod;
    380         u = f[top[u]] ;
    381     }
    382     return ans;
    383 }
    384 int main()
    385 {
    386     scanf("%d",&n) ;
    387     int P = 1;
    388     for(int i = 1;i <= n;i++) {
    389         int l , r;scanf("%d%d",&l,&r) ;
    390         in[l].push_back(i) ;
    391         out[r + 1].push_back(i) ; cm = max(cm , r);
    392         g[i] = fpow(r - l + 1 , mod - 2) ;
    393         P = 1LL * P * (r - l + 1) % mod;
    394     }
    395     for(int i = 1;i < n;i++) {
    396         int u , v;scanf("%d%d",&u,&v) ;
    397         E[u].push_back(v) ; E[v].push_back(u) ;
    398     }
    399     dfs(0 , 1 , 0) ; top[1] = 1;
    400     dfs2(0 , 1) ;
    401     build(1 , 1 , n) ;
    402     int ans = 0 , cur = 0;
    403     int d1 = 0 , d2 = 0 , u , d3 = 0;
    404     for(int i = 1;i <= cm;i++) {
    405         for(int j = 0;j < out[i].size();j++) {
    406             u = out[i][j] ;
    407             d1 = (d1 - 1LL * dep[u] * g[u] % mod + mod) % mod;
    408             d2 = (d2 - g[u] + mod) % mod ;
    409             d3 = (d3 - 1LL*dep[u]*g[u] % mod * g[u] % mod + mod) % mod;
    410             add(u , mod - g[u]) ;
    411             cur = (cur - 1LL * g[u] * cal(u) % mod + mod) % mod;
    412         }
    413         for(int j = 0;j < in[i].size();j++) {
    414             u = in[i][j] ;
    415             d1 = (d1 + 1LL * dep[u] * g[u]) % mod;
    416             d2 = (d2 + g[u]) % mod;
    417             d3 = (d3 + 1LL*dep[u]*g[u]%mod*g[u]) % mod;
    418             cur = (cur + 1LL * g[u] * cal(u)) % mod;
    419             add(u , g[u]) ;
    420         }
    421         ans = (ans + 1LL * d1 * d2%mod - 2LL*cur - d3) % mod;
    422         ans = (ans + mod) % mod;
    423     }
    424     ans = 1LL * ans * P % mod;
    425     printf("%d\n",ans);
    426     return 0;
    427 }
    428 ```