Submission #1150257

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
1150257	2025-02-14 09:43:51	nikolashami	Index (COCI21_index)	C++20	110 / 110	1175 ms	97244 KiB

index

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const ll N=2e5,N2=5+24*N;
ll root[N2],lc[N2],rc[N2],st[N2],nd;
void bd(ll lik,ll l=1,ll r=N){
  if(l==r)return;
  lc[lik]=++nd;
  rc[lik]=++nd;
  bd(lc[lik],l,(l+r)/2);
  bd(rc[lik],(l+r)/2+1,r);
}
void upd(ll pr,ll tr,ll id,ll l=1,ll r=N){
  if(l==r){st[tr]=1+st[pr];return;}
  ll md=(l+r)/2;
  if(id<=md){
    rc[tr]=rc[pr];
    lc[tr]=++nd;
    upd(lc[pr],lc[tr],id,l,md);
  }else{
    lc[tr]=lc[pr];
    rc[tr]=++nd;
    upd(rc[pr],rc[tr],id,md+1,r);
  }
  st[tr]=st[lc[tr]]+st[rc[tr]];
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 20 / 20
• Subtask 2: 40 / 40
• Subtask 3: 50 / 50