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 ```