codeforces-scrape

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

1843.md (8650B)


      1 Source: https://codeforces.com/blog/entry/117468
      2 
      3 [1843A - Sasha and Array Coloring](/contest/1843/problem/A "Codeforces Round 881 (Div. 3)")
      4 
      5 Idea: [Sokol080808](/profile/Sokol080808 "Master Sokol080808"), prepared: [molney](/profile/molney "Master molney")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution**
     12 
     13 ```
     14 def solve():
     15     n = int(input())
     16     a = [int(x) for x in input().split()]
     17     a.sort()
     18     ans = 0
     19     for i in range(n // 2):
     20         ans += a[-i-1] - a[i]
     21     print(ans)
     22     
     23     
     24 t = int(input())
     25 for _ in range(t):
     26     solve()
     27 ```
     28 
     29 **Rate the problem**
     30 
     31 * Didn't solve
     32 * Good task
     33 * Average task
     34 * Bad task
     35 
     36 [1843B - Long Long](/contest/1843/problem/B "Codeforces Round 881 (Div. 3)")
     37 
     38 Idea: [EJIC_B_KEDAX](/profile/EJIC_B_KEDAX "Master EJIC_B_KEDAX"), prepared: [molney](/profile/molney "Master molney")
     39 
     40 **Tutorial**
     41 
     42 Tutorial is loading...
     43 
     44 **Solution**
     45 
     46 ```
     47 T = int(input())
     48 for _ in range(T):
     49     n = int(input())
     50     a = list(map(int, input().split()))
     51     
     52     sum = 0
     53     cnt = 0
     54     open = False
     55     for x in a:
     56         sum += abs(x)
     57         if x < 0 and not open:
     58             open = True
     59             cnt += 1
     60         if x > 0:
     61             open = False
     62  
     63     print(sum, cnt)
     64 ```
     65 
     66 **Rate the problem**
     67 
     68 * Didn't solve
     69 * Good task
     70 * Average task
     71 * Bad task
     72 
     73 [1843C - Sum in Binary Tree](/contest/1843/problem/C "Codeforces Round 881 (Div. 3)")
     74 
     75 Idea: [Sokol080808](/profile/Sokol080808 "Master Sokol080808"), prepared: [molney](/profile/molney "Master molney")
     76 
     77 **Tutorial**
     78 
     79 Tutorial is loading...
     80 
     81 **Solution**
     82 
     83 ```
     84 t = int(input())
     85 for _ in range(t):
     86     n = int(input())
     87     s = 0
     88     while n >= 1:
     89         s += n
     90         n //= 2
     91     print(s)
     92 ```
     93 
     94 **Rate the problem**
     95 
     96 * Didn't solve
     97 * Good task
     98 * Average task
     99 * Bad task
    100 
    101 [1843D - Apple Tree](/contest/1843/problem/D "Codeforces Round 881 (Div. 3)")
    102 
    103 Idea: [EJIC_B_KEDAX](/profile/EJIC_B_KEDAX "Master EJIC_B_KEDAX"), prepared: [Vladosiya](/profile/Vladosiya "Expert Vladosiya")
    104 
    105 **Tutorial**
    106 
    107 Tutorial is loading...
    108 
    109 **Solution**
    110 
    111 ```
    112 #include <bits/stdc++.h>
    113 using namespace std;
    114 typedef long long ll;
    115  
    116 vector<vector<int>> g;
    117 vector<ll> cnt;
    118  
    119 void dfs(int v, int p) {
    120     if (g[v].size() == 1 && g[v][0] == p) {
    121         cnt[v] = 1;
    122     } else {
    123         for (auto u : g[v]) {
    124             if (u != p) {
    125                 dfs(u, v);
    126                 cnt[v] += cnt[u];
    127             }
    128         }
    129     }
    130 }
    131  
    132 void solve() {
    133     int n, q;
    134     cin >> n;
    135  
    136     g.assign(n, vector<int>());
    137     
    138     for (int i = 0; i < n - 1; i++) {
    139         int u, v;
    140         cin >> u >> v;
    141         u--; v--;
    142         g[u].push_back(v);
    143         g[v].push_back(u);
    144     }
    145  
    146     cnt.assign(n, 0);
    147     dfs(0, -1);
    148  
    149     cin >> q;
    150     for (int i = 0; i < q; i++) {
    151         int c, k;
    152         cin >> c >> k;
    153         c--; k--;
    154  
    155         ll res = cnt[c] * cnt[k];
    156         cout << res << '\n';
    157     }
    158 }
    159  
    160 signed main() {
    161     int tests;
    162     cin >> tests;
    163     while (tests--) {
    164         solve();
    165     }
    166  
    167     return 0;
    168 }
    169 ```
    170 
    171 **Rate the problem**
    172 
    173 * Didn't solve
    174 * Good task
    175 * Average task
    176 * Bad task
    177 
    178 [1843E - Tracking Segments](/contest/1843/problem/E "Codeforces Round 881 (Div. 3)")
    179 
    180 Idea: [meowcneil](/profile/meowcneil "Master meowcneil"), prepared: [meowcneil](/profile/meowcneil "Master meowcneil")
    181 
    182 **Tutorial**
    183 
    184 Tutorial is loading...
    185 
    186 **Solution**
    187 
    188 ```
    189 def solve():
    190     n, m = map(int, input().split())
    191     segs = []
    192     for i in range(m):
    193         l, r = map(int, input().split())
    194         l -= 1
    195         segs.append([l, r])
    196     q = int(input())
    197     ord = [0] * q
    198     for i in range(q):
    199         ord[i] = int(input())
    200         ord[i] -= 1
    201     l = 0
    202     r = q + 1
    203     while r - l > 1:
    204         M = (l + r) // 2
    205         cur = [0] * n
    206         for i in range(M):
    207             cur[ord[i]] = 1
    208         pr = [0] * (n + 1)
    209         for i in range(n):
    210             pr[i+1] = pr[i] + cur[i]
    211         ok = False
    212         for i in segs:
    213             if(pr[i[1]] - pr[i[0]] > (i[1] - i[0]) // 2):
    214                 ok = True
    215                 break
    216         if ok:
    217             r = M
    218         else:
    219             l = M
    220     if r == q + 1:
    221         r = -1
    222     print(r)
    223  
    224 tc = int(input())
    225 for T in range(tc):
    226     solve()
    227 ```
    228 
    229 **Rate the problem**
    230 
    231 * Didn't solve
    232 * Good task
    233 * Average task
    234 * Bad task
    235 
    236 [1843F1 - Omsk Metro (simple version)](/contest/1843/problem/F1 "Codeforces Round 881 (Div. 3)")
    237 
    238 Idea: [EJIC_B_KEDAX](/profile/EJIC_B_KEDAX "Master EJIC_B_KEDAX"), prepared: [Sokol080808](/profile/Sokol080808 "Master Sokol080808")
    239 
    240 **Tutorial**
    241 
    242 Tutorial is loading...
    243 
    244 **Solution**
    245 
    246 ```
    247 class info:
    248     mn_suf = 0
    249     mx_suf = 0
    250     mn_ans = 0
    251     mx_ans = 0
    252  
    253 def solve():
    254     n = int(input())
    255     
    256     start = info()
    257     start.mx_suf = start.mx_ans = 1
    258     
    259     st = [start]
    260     for i in range(n):
    261         com = input().split()
    262         if (com[0] == '+'):
    263             v = int(com[1]) - 1
    264             x = int(com[2])
    265  
    266             pref = st[v]
    267             cur = info()
    268  
    269             cur.mn_suf = min(0, pref.mn_suf + x)
    270             cur.mx_suf = max(0, pref.mx_suf + x)
    271             cur.mn_ans = min(pref.mn_ans, cur.mn_suf)
    272             cur.mx_ans = max(pref.mx_ans, cur.mx_suf)
    273  
    274             st.append(cur)
    275         else:
    276             v = int(com[2]) - 1
    277             x = int(com[3])
    278  
    279             if st[v].mn_ans <= x <= st[v].mx_ans:
    280                 print("Yes")
    281             else:
    282                 print("No")
    283  
    284 t = int(input())
    285 for testCase in range(t):
    286     solve()
    287 ```
    288 
    289 **Rate the problem**
    290 
    291 * Didn't solve
    292 * Good task
    293 * Average task
    294 * Bad task
    295 
    296 [1843F2 - Omsk Metro (hard version)](/contest/1843/problem/F2 "Codeforces Round 881 (Div. 3)")
    297 
    298 Idea: [EJIC_B_KEDAX](/profile/EJIC_B_KEDAX "Master EJIC_B_KEDAX"), prepared: [Sokol080808](/profile/Sokol080808 "Master Sokol080808")
    299 
    300 **Tutorial**
    301 
    302 Tutorial is loading...
    303 
    304 **Solution**
    305 
    306 ```
    307 #include <bits/stdc++.h>
    308  
    309 using namespace std;
    310  
    311 typedef long long ll;
    312  
    313 struct info {
    314     int sum, minPrefL, maxPrefL, minPrefR, maxPrefR, minSeg, maxSeg;
    315  
    316     info(int el = 0) {
    317         sum = el;
    318         minSeg = minPrefL = minPrefR = min(el, 0);
    319         maxSeg = maxPrefL = maxPrefR = max(el, 0);
    320     }
    321 };
    322  
    323 struct question {
    324     int u, v, x;
    325 };
    326  
    327 info merge(info& a, info& b) {
    328     info res;
    329     res.sum = a.sum + b.sum;
    330     res.minPrefL = min(a.minPrefL, a.sum + b.minPrefL);
    331     res.maxPrefL = max(a.maxPrefL, a.sum + b.maxPrefL);
    332     res.minPrefR = min(a.minPrefR + b.sum, b.minPrefR);
    333     res.maxPrefR = max(a.maxPrefR + b.sum, b.maxPrefR);
    334     res.minSeg = min({a.minSeg, b.minSeg, a.minPrefR + b.minPrefL});
    335     res.maxSeg = max({a.maxSeg, b.maxSeg, a.maxPrefR + b.maxPrefL});
    336     return res;
    337 }
    338  
    339 const int MAXN = 200100;
    340 const int lg = 17;
    341  
    342 int up[lg + 1][MAXN];
    343 info ans[lg + 1][MAXN];
    344 int d[MAXN];
    345  
    346 void solve() {
    347     int n;
    348     cin >> n;
    349  
    350     for (int i = 0; i <= lg; i++) up[i][0] = 0;
    351     ans[0][0] = info(1);
    352     d[0] = 0;
    353  
    354     int cur = 0;
    355     for (int q = 0; q < n; q++) {
    356         char c;
    357         cin >> c;
    358         if (c == '+') {
    359             int v, x;
    360             cin >> v >> x;
    361             v--;
    362             cur++;
    363  
    364             d[cur] = d[v] + 1;
    365  
    366             up[0][cur] = v;
    367             for (int j = 0; j <= lg - 1; j++) up[j + 1][cur] = up[j][up[j][cur]];
    368  
    369             ans[0][cur] = info(x);
    370             for (int j = 0; j <= lg - 1; j++) ans[j + 1][cur] = merge(ans[j][cur], ans[j][up[j][cur]]);
    371         } else {
    372             int u, v, x;
    373             cin >> u >> v >> x;
    374             u--; v--;
    375             
    376             if (d[u] < d[v]) swap(u, v);
    377  
    378             int dif = d[u] - d[v];
    379             info a, b;
    380             for (int i = lg; i >= 0; i--) {
    381                 if ((dif >> i) & 1) {
    382                     a = merge(a, ans[i][u]);
    383                     u = up[i][u];
    384                 }
    385             }
    386  
    387             if (u == v) {
    388                 a = merge(a, ans[0][u]);
    389             } else {
    390                 for (int i = lg; i >= 0; i--) {
    391                     if (up[i][u] != up[i][v]) {
    392                         a = merge(a, ans[i][u]);
    393                         u = up[i][u];
    394                         b = merge(b, ans[i][v]);
    395                         v = up[i][v];
    396                     }
    397                 }
    398  
    399                 a = merge(a, ans[1][u]);
    400                 b = merge(b, ans[0][v]);
    401             }
    402  
    403             swap(b.minPrefL, b.minPrefR);
    404             swap(b.maxPrefL, b.maxPrefR);
    405  
    406             info res = merge(a, b);
    407             if (res.minSeg <= x && x <= res.maxSeg) {
    408                 cout << "Yes\n";
    409             } else {
    410                 cout << "No\n";
    411             }
    412         }
    413     }
    414 }
    415  
    416 int main() {
    417     int tests;
    418     cin >> tests;
    419     while (tests--) {
    420         solve();
    421     }
    422 }
    423 ```
    424 
    425 **Rate the problem**
    426 
    427 * Didn't solve
    428 * Good task
    429 * Average task
    430 * Bad task