Codeforces Round #881 (Div. 3) Разбор

№	Пользователь	Рейтинг
1	tourist	3690
2	jiangly	3647
3	Benq	3581
4	orzdevinwang	3570
5	Geothermal	3569
5	cnnfls_csy	3569
7	Radewoosh	3509
8	ecnerwala	3486
9	jqdai0815	3474
10	gyh20	3447

№	Пользователь	Вклад
1	maomao90	174
2	awoo	164
3	adamant	162
4	TheScrasse	159
5	nor	157
6	maroonrk	156
7	-is-this-fft-	152
8	orz	146
9	Petr	145
9	pajenegod	145

Идея: Sokol080808, разработка: molney

Разбор

Решение

def solve():
    n = int(input())
    a = [int(x) for x in input().split()]
    a.sort()
    ans = 0
    for i in range(n // 2):
        ans += a[-i-1] - a[i]
    print(ans)
    
    
t = int(input())
for _ in range(t):
    solve()

Оценка задачи

1843B - Лонг лонг

Идея: EJIC_B_KEDAX, разработка: molney

Разбор

Решение

T = int(input())
for _ in range(T):
    n = int(input())
    a = list(map(int, input().split()))
    
    sum = 0
    cnt = 0
    open = False
    for x in a:
        sum += abs(x)
        if x < 0 and not open:
            open = True
            cnt += 1
        if x > 0:
            open = False
 
    print(sum, cnt)

Оценка задачи

1843C - Сумма в бинарном дереве

Идея: Sokol080808, разработка: molney

Разбор

Решение

t = int(input())
for _ in range(t):
    n = int(input())
    s = 0
    while n >= 1:
        s += n
        n //= 2
    print(s)

Оценка задачи

1843D - Яблоня

Идея: EJIC_B_KEDAX, разработка: Vladosiya

Разбор

Решение

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
vector<vector<int>> g;
vector<ll> cnt;
 
void dfs(int v, int p) {
    if (g[v].size() == 1 && g[v][0] == p) {
        cnt[v] = 1;
    } else {
        for (auto u : g[v]) {
            if (u != p) {
                dfs(u, v);
                cnt[v] += cnt[u];
            }
        }
    }
}
 
void solve() {
    int n, q;
    cin >> n;
 
    g.assign(n, vector<int>());
    
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        u--; v--;
        g[u].push_back(v);
        g[v].push_back(u);
    }
 
    cnt.assign(n, 0);
    dfs(0, -1);
 
    cin >> q;
    for (int i = 0; i < q; i++) {
        int c, k;
        cin >> c >> k;
        c--; k--;
 
        ll res = cnt[c] * cnt[k];
        cout << res << '\n';
    }
}
 
signed main() {
    int tests;
    cin >> tests;
    while (tests--) {
        solve();
    }
 
    return 0;
}

Оценка задачи

1843E - Слежка за отрезками

Идея: meowcneil, разработка: meowcneil

Разбор

Решение

def solve():
    n, m = map(int, input().split())
    segs = []
    for i in range(m):
        l, r = map(int, input().split())
        l -= 1
        segs.append([l, r])
    q = int(input())
    ord = [0] * q
    for i in range(q):
        ord[i] = int(input())
        ord[i] -= 1
    l = 0
    r = q + 1
    while r - l > 1:
        M = (l + r) // 2
        cur = [0] * n
        for i in range(M):
            cur[ord[i]] = 1
        pr = [0] * (n + 1)
        for i in range(n):
            pr[i+1] = pr[i] + cur[i]
        ok = False
        for i in segs:
            if(pr[i[1]] - pr[i[0]] > (i[1] - i[0]) // 2):
                ok = True
                break
        if ok:
            r = M
        else:
            l = M
    if r == q + 1:
        r = -1
    print(r)
 
tc = int(input())
for T in range(tc):
    solve()

Оценка задачи

1843F1 - Метрополитен в Омске (простая версия)

Идея: EJIC_B_KEDAX, разработка: Sokol080808

Разбор

Решение

class info:
    mn_suf = 0
    mx_suf = 0
    mn_ans = 0
    mx_ans = 0
 
def solve():
    n = int(input())
    
    start = info()
    start.mx_suf = start.mx_ans = 1
    
    st = [start]
    for i in range(n):
        com = input().split()
        if (com[0] == '+'):
            v = int(com[1]) - 1
            x = int(com[2])
 
            pref = st[v]
            cur = info()
 
            cur.mn_suf = min(0, pref.mn_suf + x)
            cur.mx_suf = max(0, pref.mx_suf + x)
            cur.mn_ans = min(pref.mn_ans, cur.mn_suf)
            cur.mx_ans = max(pref.mx_ans, cur.mx_suf)
 
            st.append(cur)
        else:
            v = int(com[2]) - 1
            x = int(com[3])
 
            if st[v].mn_ans <= x <= st[v].mx_ans:
                print("Yes")
            else:
                print("No")
 
t = int(input())
for testCase in range(t):
    solve()

Оценка задачи

1843F2 - Метрополитен в Омске (сложная версия)

Идея: EJIC_B_KEDAX, разработка: Sokol080808

Разбор

Решение

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
struct info {
    int sum, minPrefL, maxPrefL, minPrefR, maxPrefR, minSeg, maxSeg;
 
    info(int el = 0) {
        sum = el;
        minSeg = minPrefL = minPrefR = min(el, 0);
        maxSeg = maxPrefL = maxPrefR = max(el, 0);
    }
};
 
struct question {
    int u, v, x;
};
 
info merge(info& a, info& b) {
    info res;
    res.sum = a.sum + b.sum;
    res.minPrefL = min(a.minPrefL, a.sum + b.minPrefL);
    res.maxPrefL = max(a.maxPrefL, a.sum + b.maxPrefL);
    res.minPrefR = min(a.minPrefR + b.sum, b.minPrefR);
    res.maxPrefR = max(a.maxPrefR + b.sum, b.maxPrefR);
    res.minSeg = min({a.minSeg, b.minSeg, a.minPrefR + b.minPrefL});
    res.maxSeg = max({a.maxSeg, b.maxSeg, a.maxPrefR + b.maxPrefL});
    return res;
}
 
const int MAXN = 200100;
const int lg = 17;
 
int up[lg + 1][MAXN];
info ans[lg + 1][MAXN];
int d[MAXN];
 
void solve() {
    int n;
    cin >> n;
 
    for (int i = 0; i <= lg; i++) up[i][0] = 0;
    ans[0][0] = info(1);
    d[0] = 0;
 
    int cur = 0;
    for (int q = 0; q < n; q++) {
        char c;
        cin >> c;
        if (c == '+') {
            int v, x;
            cin >> v >> x;
            v--;
            cur++;
 
            d[cur] = d[v] + 1;
 
            up[0][cur] = v;
            for (int j = 0; j <= lg - 1; j++) up[j + 1][cur] = up[j][up[j][cur]];
 
            ans[0][cur] = info(x);
            for (int j = 0; j <= lg - 1; j++) ans[j + 1][cur] = merge(ans[j][cur], ans[j][up[j][cur]]);
        } else {
            int u, v, x;
            cin >> u >> v >> x;
            u--; v--;
            
            if (d[u] < d[v]) swap(u, v);
 
            int dif = d[u] - d[v];
            info a, b;
            for (int i = lg; i >= 0; i--) {
                if ((dif >> i) & 1) {
                    a = merge(a, ans[i][u]);
                    u = up[i][u];
                }
            }
 
            if (u == v) {
                a = merge(a, ans[0][u]);
            } else {
                for (int i = lg; i >= 0; i--) {
                    if (up[i][u] != up[i][v]) {
                        a = merge(a, ans[i][u]);
                        u = up[i][u];
                        b = merge(b, ans[i][v]);
                        v = up[i][v];
                    }
                }
 
                a = merge(a, ans[1][u]);
                b = merge(b, ans[0][v]);
            }
 
            swap(b.minPrefL, b.minPrefR);
            swap(b.maxPrefL, b.maxPrefR);
 
            info res = merge(a, b);
            if (res.minSeg <= x && x <= res.maxSeg) {
                cout << "Yes\n";
            } else {
                cout << "No\n";
            }
        }
    }
}
 
int main() {
    int tests;
    cin >> tests;
    while (tests--) {
        solve();
    }
}

Оценка задачи

visited[apple] = 1; for(auto it = adj[apple].begin();it<adj[apple].end();it++){ if(!visited[*it]){ dfs(*it); leaves[apple]+=leaves[*it]; } // else leaves[apple]+=leaves[*it]; } if(adj[apple].empty()){ leaves[apple]++; // cout<<"Leaves["<<apple<<"] is : "<<leaves[apple]<<"\n"; // visited[apple] = 0; return; } // cout<<"Leaves["<<apple<<"] is : "<<leaves[apple]<<"\n"; // visited[apple] = 0; return;

map<int,vector<pair<int/*second node*/,int/*weight*/>>>graph; pair<int,int> segments[2][N]; int vis[N]; void dfs(int node,int sum,int mx_sum,int mn_sum){ vis[node]=1; for(auto child:graph[node]) { if (!vis[child.first]) { if (child.second == 1) { int val = sum >= 1 ? sum : 0; segments[1][child.first].second = mn_sum; segments[1][child.first].first = max(mx_sum, val + 1); dfs(child.first, val + 1, max(mx_sum, val + 1), mn_sum); } else { int val = sum <= -1 ? sum : 0; segments[1][child.first].second = min(val - 1, mn_sum); segments[1][child.first].first = mx_sum; dfs(child.first, val - 1, mx_sum, min(mn_sum, val - 1)); } } } } void solve() { int cnt=1; int n,size;cin>>n; vector<pair<int,int>>queries; graph.clear(); for(int i=0;i<n;++i){ char t; cin>>t; if(t=='?') { int a, b, val; cin>>a>>b>>val; queries.emplace_back(b,val); } else{ int node,weight;cin>>node>>weight; graph[node].emplace_back(cnt+1,weight); graph[++cnt].emplace_back(node,weight); } } for(int i=1;i<=cnt;++i)vis[i]=0; for(int i=1;i<=cnt;++i) segments[1][i]={1,0}; dfs(1,1,1,0); size=queries.size(); for(int i=0;i<size;++i){ int b=queries[i].first,weight=queries[i].second; cout<<(weight>=segments[1][b].second&&weight<=segments[1][b].first?"YES\n":"NO\n"); } }

#include <bits/stdc++.h> using namespace std; int dfs(vector<int>*T,int* pos, int node,int par){ if(T[node].size()==1 && T[node][0]==par){ pos[node]=1; return 1; } int paths=0; for(auto n:T[node]){ if(n!=par){ paths+=dfs(T,pos,n,node); } } pos[node]=paths; return paths; } int main(){ int t; cin>>t; while(t--){ int n; cin>>n; vector<int> T[n]; int pos[n] = {0}; for(int i=0;i<n-1;i++){ int u,v; cin>>u>>v; T[u-1].emplace_back(v-1); T[v-1].emplace_back(u-1); } dfs(T,pos,0,-1); int Q; cin>>Q; unsigned long long int ans; while(Q--){ int s,t; cin>>s>>t; ans=pos[s-1]*pos[t-1]; cout<<ans<<'\n'; } } return 0; }

from collections import defaultdict def solve(tree, node): if len(tree[node]) == 0: return 1 sm = 0 for child in tree[node]: sm += solve(tree, child) return sm for _ in range(int(input())): n = int(input()) tree = defaultdict(set) for _ in range(n - 1): u, v = map(int, input().split()) if v < u: u, v = v, u tree[u].add(v) q = int(input()) for _ in range(q): x, y = map(int, input().split()) res = solve(tree, x) * solve(tree, y) print(res)

Комментарии (111)

Написать комментарий?

Sokol080808

11 месяцев назад, # |

Автокомментарий: текст был обновлен пользователем Sokol080808 (предыдущая версия, новая версия, сравнить).

→ Ответить

BlackHole

Nice! The tutorial has came out!

Mehanalavi

Good contest. Ah Why I didn't think of int overflow

vgtcross

11 месяцев назад, # ^ |

You should try to read statements more carefully. At the end of the output section in B was stated:

"Pay attention that an answer may not fit in a standard integer type, so do not forget to use 64-bit integer type."

And also, the problem name was a hint :)

polosatic

Or just use #define int long long

you_xiao

that's so good. XD

jjjfr

9 месяцев назад, # ^ |

I think so.

induwara16

i had the same problem but then realized the problem name is literally long long

MikhailKapitov

+53

Once again, thank you for this fun contest! :D

mrphyx1312

Why does my code output 0 in all queries in D problem? Submission Id: 210522059 ~~~~~ void dfs(int apple){

}

~~~~~

_maniac_

← Rev. 2 →

It is because of the way you are reading the graphs as input, you are making the larger vertex number the child and the smaller one the parent which is not always true

Finral_eCia

You using directed graph instead of undirected graph. While you run dfs only for vertex 1. Consider an graph:

where your vector list represent like that

1 -> 3

2 -> 3 , 4 , 5

Now see your dfs start from 1 then 3 and then it was stopped. because there are no connection from 3. So leaves array are not changed. Just changes in directed to undirected, your code will pass the cases. if you use undirected graph then the vector list look like —

3 -> 1, 2

4 -> 2

5 -> 2

then your dfs will run for all the vertex, and compute leaves array.

When I remove the conditions I get a segmentation fault and it then outputs 0 on everything.

When I remove the conditions I get a segmentation fault and it then outputs 0 on everything., does using the vector of vectors cause the issue??

Furthermore when I keep the conditional statements, the code outputs correctly up to test case 4

ritesh_gupta97

You may have a look at this implementation 210483045

FortuneWillWinICPC

+19

I've learned to use binary lifting to store more information thanks to the problem F, really good contest

Aswathama.

10 месяцев назад, # ^ |

can you explain how you have used binary lifting

For each node, let's store for it some informations, consider the path start from the node to its 2^k-th parents, we store the maximum prefix, suffix, the sum of whole path, and the maximum sum, we can efficiently use these informations to combine the path with another path.

To get similar with this concept, I suggest you to have a look at the Segment Tree course in Codeforces Edu section, which also have this concept but for an array.

Bronya147

nice round,hope for the positive del:)

dhruv1807

Can someone tell me why my code was giving TLE for 1843D - Apple Tree. All I did was globally define the graph and cnt array similar to the tutorial solution and it worked then.

This is my initial submission: 210536302. This is the final accepted submission: 210538893

Passing the whole graph as an argument for the helper function each time is costly. C++ basically has to make a new copy of it each time you call that function. After making g global, it no longer has to do this. Alternatively, you could've passed a pointer to the graph as an argument.

Okay, thanks!

OmarAboutaleb77

For problem E, why don’t you need a prefix sum for every possible array. I understand the binary search part but just building the prefix sums would tle right?

SriniV

← Rev. 3 →

Analyzing the complexity : You binary search on q ( O(log(q)) ) and to check if a certain value is valid, you build the prefix sum array and then iterate through segments ( O(m + n (+q depending on impl) ) ). Combining these, you get O(log(q)(m+n)). If you were to build all prefix sum arrays before hand, that would take you O(q*n) time ( TLE ), because for each query, you would have to build prefix-suns. A way around this is to use a segment tree to achieve O(qlog(n)) for precomputation!

Thank you for your explanation. I forgot we could build the prefix sums inside of the binary search :(.

Rad1x

As we are populating the prefix array while we are doing binary search, the maximum number of times we would have to create the prefix array would be O(log Q) and creating each prefix array would take O(N) time, thus total time complexity will be well under limits reaching only O(N*log Q) for prefix array creation and O(M*log Q) for checking every range given to us, making the total time complexity O((N+M)*log Q).

Jack_sparrow_06

For the problem C, I tried to find the path from the vertex 1 to vertex n, using the bits values, but not able to solve it :( . Do there exist any solution related to bits for it ?

For the problem C, I tried to solve the problem by find the values from the vertex 1, and using the bit value of 'N' to decide to go for either left subtree or right subtree, but I couldn't solve it :( . Does there exist any solution by using the bit value of 'N' to find either to go left or right ?

atomicapple0

My solution does that in Python. You could do the same in another language with bitwise operators like shifts and masks.

Submission: 210386925

Do you go from the least significant bit to most significant or vice versa ?

Msb to lsb

Thanks for the help.

__Waled

-11

can someone provide me any hints to detect the error in my code in problem F1?

i fall on test 3 on line 11301st expected yes found no

t1400

same error bro

-8

+ 1 1
+ 2 -1
+ 3 1
+ 2 -1
+ 4 1 
+ 2 -1

and the query is

? 1 6 3

should be no only for this

actually it's yes because there is a subsegment from 1 to 6 that actually add up to 3

node 1 ==> 1 node 2 ==> 1 node 3 ==> -1 node 4 ==> 1 node 6 ==> 1

this adds up to 3

yes bro spot on. Actually i counted max positive sum on a path as only th length of consecutive ones and set it to 0 again when -1 came in between while this is nt crct as evident feom this tc.such a fool i am

Ayo bro i did the same XD , i totally forget that not only the consecutive needs to be added Actually this problem is just literally find the maximum and minimum sum of subsegments in array At least we learnt new something today Hope for cyan next div me and you <3

210560633 why this is giving me a wa although i have gone with the correct logic

Tomatos03

I don't know how the tree given in the example in question D is drawn, can someone explain it to me, thank you very much.

atharvd

This is the first testcase:

5 1 2 3 4 5 3 3 2 4 3 4 5 1 4 4 1 3

The first number is n, so there are n — 1 edges with follow. Let us start with the first edge. "1 2" means an edge is drawn between vertices 1 and 2 (depicted by a line connected 1 and 2). We do the same for edges "3 4", "5 3", and "3 2".

tyagsa

My solution for F2 https://youtu.be/FZJxWhOoxo0

dushsam

I was not able to make it in this round as I planned. But hope things will be great next time.

lrvideckis

E can be solved with wavelet tree:

create an array, initially all INF. then for the ith update, set array[index] = i

now for each segment, the (segment len/2 + 1)th-smallest number is either INF, or the id of the query which makes it beautiful

210572758

Shubham247

Any solution possible with — segment trees concept only ?

ignite312

Yes, Check my submission 210447265, (By using Segment tree + Binary Search approach)

Thallium54

It boils down to finding k-th smallest element in a range, there's a lot of ways of doing it: wavelet tree, persistent segment tree, parallel binary search...

pocket_acer

persistent segment tree gave me mle -_-

Checkout my implementation 210606529

For me — no: 210400778

I used other idea, but I believe your PST can be optimized, too)

hhvmegyy

I solved E during the contest using wavelet tree too, I'm looking for the (len/2 + 1 + (number of zeros))th-smallest in each segment

my submission: 210413964

B_Consistent

4 месяца назад, # ^ |

I guess wavlet tree is better than the Editorial solution

lvisbl_

Can some one help me with the fourth test case, why my solution is wrong.. My intuitive is exactly the same with the editorial, I count the number of leaf node with DFS and count it by a Set (in case multiple parts reach the same leaf node). But I can not solve the fourth test case. I use JavaScript, sorry for the inconvenience. My submission

I tried a persistent segment tree approach in E but got mle. Since I copied the implementation from cpp-algorithms I didn't know how to delete all the nodes to free up space after each tc. Does anyone uses persistent segment trees at all for cp? It used 200mbs for trivial test cases so I wonder if they are useful in cp contests at all?

AnyOne tried to use — segment trees ? for problem E

yadavDipesh

code

Thanks for the code

sambhrant_07

210691219 I have used merge sort tree You can also solve MKTHNUM — K-th Number SPOJ LINK This concept is used in this problem

Thanks for sharing

pragunb02

Time Complexity for E would be : O((q+n+m)⋅logq)

Epilogue

In F1 and F2 the realize that you only need to find maximum and minimum sum can create make everything much easier.

UnreliableSpare

Quite instructive contest. Thank you.

-ved-ansh-

I am struggling hard to figure out what's wrong with my code for problem D.210612596 Unlike other solutions, I have only connected nodes u and v from u to v such that u < v. I am guessing that's the bug but I am not sure exactly how.

pcajourney

What's your logic to add edge u->v only if u < v ??

From what I thought after reading the testcases is that when an edge v1, v2 is given and v1 < v2, then that means v1 is the parent node of v2, otherwise v2 is the parent node. So I made a directed adjacency list such that adj[v] contains only the nodes which are it's children. Using this, finding the leafnodes is simple as adj[v] will be empty if v is leafnode.

"From what I thought after reading the testcases is that when an edge v1, v2 is given and v1 < v2, then that means v1 is the parent node of v2, otherwise v2 is the parent node."

That's the problem: You assumed something that wasn't guranteed in the statement. The assumption that smaller vertices are parents of larger ones is incorrect. You need to treat the given tree as a graph of undirected edges and find the parent nodes yourself (if you need them).

sumj25

Does anyone solve it using sqrt decomposition for problem E?

induk_v_tsiane

You can also solve F2 with HLD for the same reason, if you could not figure out (like me) how to do it with binlifts. Code: https://codeforces.com/contest/1843/submission/210677217

I'm trying the HLD approach but I'm keeping it WA at test 3, here is my submission: 210725677. Could you help me to point out where am I missing, thanks.

ctrller

8 месяцев назад, # ^ |

Hi I am curious how did you avoid stack overflow when running dfs? I tried HLD approach but still stuck at testcase 3 with Runtime error due to stack overflow

ethico

good problems

Minhazur

Did not understand the editorial of 1843E - Tracking Segments. Can anyone help me understand it please..

TsupaRoman

You can try to write some problems about binary search, it's can help you

prathyand

Can someone explain why this doesn't work? I get wrong answer error for testcase 8

your pos array is int type. You need to change it to long long or type cast it before multiplying. Because after multiplying, it is returning int and then the int is getting converted into long long.

quick fix should be ans = (long long int)pos[s-1] * pos[t-1];

thanks !

hyh13566501125

为什么没有C++的题解

parseee

Can anybody tell me why in E in the first test when we change 5-th element in array on 1, it doesn't count as a solution? I mean that we have a segment (5 5) and if we change 5-th element we have 0 zeroes and 1 one...

sanidhyas3s

You have to only consider the segments given in the input and not any segment.

Thank you, but i meant that in input we have (5, 5) segment and it fits with the first query...

No that is actually n and m.

Oh, that's dumb... thank you, didn't even noticed it...

antsparrow5

nice contest

hodgsontet

Iam suprised at how people can come up with the greedy algorithm so fast , the only explanation is they must have seen a question like that before.

Nivalderramas

Yup, that's right

myy04

Can someone help me debug my solution for F2? https://codeforces.com/contest/1843/submission/211222013

WA on the third test (180th token)

iamcclocation

211316049 Can anyone tell me why this code results in Exit code is-1073741571.thanks.

211316102 This code gets Accept.

ivan100sic

+23

An even shorter solution for C: 2*x - popcount(x)

reilu

Is this formula derived purely from observation or is there some intuition to it?

Intuition is what I used to find this solution, but it can be easily proven using basic number theory.

Can you give some hints about the intuition behind it?

the_hyp0cr1t3

Consider the contribution of each bit to the answer $$$\sum \lfloor \frac{n}{2^k} \rfloor$$$. If the $$$j$$$-th bit is set in $$$n$$$, the $$$(j-1)$$$-th bit will be set in $$$\lfloor \frac{n}{2} \rfloor$$$, the $$$(j-2)$$$-th bit will be set in $$$\lfloor \frac{n}{4} \rfloor$$$ and so on until $$$(j-j)=0$$$-th bit is set. We also know that $$$\sum_{0 \le k \le j} 2^k = 2^{j+1}-1$$$.

Putting everything together, you get $$$2 \cdot n - (\text{no. of set bits in } n)$$$.

__kan_dup

In problem E, my code works in O((m+q)logm) time in the average case. Still, it gives TLE, and I am frustrated. There are many instances where my correct code gives TLE in C++; then, when I convert them line by line to Python, the code runs without error. It is frustrating.

abhishek7997

10 месяцев назад, # |

Hi everyone.

Can anyone please explain why my code is giving WRONG_ANSWER on problem D?

211679589

yash2603

I am getting stack overflow error for my submission:https://codeforces.com/contest/1843/submission/211281258 I have set maxim recursion limit for python what should i do, please hep

aroncode

Can anyone pls tell me why in sol for F2 the parent of LCA is also merged??

Thanks in Advanced.

siliconrhino

Can anyone tell why this solution 212190931 or this 212172518 shows memory limit exceeded for problem F1

MADHAV_GOEL

Can anyone please tell why this solution gives TLE on test case 5

https://codeforces.com/contest/1843/submission/213606130

Thanks

memset(ans, -1, sizeof((ans)));

Can you please elaborate ?

kgb_70

why my code works for first 4 cases but then gives different result, even though the logic is correct. code

d1mk

+10

Instead of int try using long long, because answer may be greater than the size of int (2^31 = 2147483648) 214366788

thanks, it worked.

Rayan.

Good contest

_DuMoH4uK_

I solved E using K-th order statistics on segment. Let's sort queries by X. For each segment (let it be [l, r]) we use binary search to find all queries, laying on it. Easy to understand these queries form a segment (let this segment be [l1, r1]). Suppose K = (r-l+1) / 2 + 1 (it's the number of 1 for segment to become beautiful). Then we are to find on segment [l1, r1] the number of query, which would be on position K, if we sorted these queries by their numbers.

P.S. Yeah, you can tell me I'm sick)

m_nigam01

7 месяцев назад, # |

Hello, I am able to understand the D. Apple Tree logic. When i coded it in python i'm getting runtime error in python https://codeforces.com/contest/1843/submission/230310579. but the same code when converted using gpt passes the judge. What could be the error here. I think recursion is the issue here. but writing loop solution i'm not able to do. can i make this python solution pass the judge?

4 месяца назад, # |

when will Div3 change by not givving horrible implementation in last question They just dump it inot div3

Блог пользователя Sokol080808