打卡信奥刷题（3311）用C++实现信奥题 P9176 [COCI 2022/2023 #4] Vrsta

P9176 [COCI 2022/2023 #4] Vrsta题目描述Domagoj 最喜欢的课是体育课。每节体育课都以热身运动开始。体育老师有一个有趣的方法来选择带领其他同学做热身运动的学生。学生们按身高从低到高的顺序站成一排老师会选择站在队伍中间的学生。如果有两个学生在中间他将选择较矮的那个。例如如果学生的身高为1,3,5,7,111, 3, 5, 7, 111,3,5,7,11身高为555的学生将带领其他同学做热身运动。Domagoj 记不住他同学的身高。幸运的是站在他旁边的 Lovro 十分擅长估计他人的身高。他给了 Domagojnnn条信息「有aia_iai​个身高为viv_ivi​的学生进入了体育馆。」在 Lovro 说完每条信息之后Domagoj 都对带领其他同学做热身运动的那个同学的身高感兴趣。假定所有进入体育馆的同学都是来上体育课的。请帮他回答他的问题输入格式第一行一个整数n (1≤n≤200 000)n\ (1\le n\le 200\ 000)n(1≤n≤200000)表示 Lovro 的信息条数。接下来nnn行包含两个整数vi,ai (1≤vi,ai≤109)v_i,a_i\ (1\le v_i,a_i\le 10^9)vi​,ai​(1≤vi​,ai​≤109)表示 Lovro 所给信息中的身高和人数。输出格式输出nnn行表示在 Lovro 给出第iii条信息后对 Domagoj 问题的回答。输入输出样例 #1输入 #13 2 1 3 1 1 1输出 #12 2 2输入输出样例 #2输入 #24 17 2 23 5 11 4 9 5输出 #217 23 17 11输入输出样例 #3输入 #33 10 20 100 5 1000 5输出 #310 10 10说明/提示子任务编号附加限制分值000是样例000111n,vi≤1000n,v_i\le 1000n,vi​≤1000171717222a1a2…an1a_1a_2\ldotsa_n1a1​a2​…an​1242424333v1v2…vnv_1v_2\ldots v_nv1​v2​…vn​262626444无附加限制333333C实现#includebits/stdc.h#defineN200001#defineintlonglong//十年 OI 一场空usingnamespacestd;intn,sum;intv[N],a[N],b[N],c[N];voidadd(intx,intk){for(intix;in;ii(-i)){c[i]k;}}intqry(intx){intcnt0;for(intix;i;i-i(-i)){cntc[i];}returncnt;}intbin(){intl1,rn;while(lr){intmid(lr)1;if(qry(mid)(sum1)/2){rmid-1;}else{lmid1;}}returnl;}signedmain(){cinn;for(inti1;in;i){cinv[i]a[i];b[i]v[i];}sort(b1,bn1);for(inti1;in;i){v[i]lower_bound(b1,bn1,v[i])-b;//离散化suma[i];//更新当前人数add(v[i],a[i]);//维护前缀和coutb[bin()]endl;//注意二分的答案是离散化后的需要还原}return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容