Submission #405394

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
405394	2021-05-16 10:38:40	Sundavar	Index (COCI21_index)	C++14	110 / 110	1172 ms	137196 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;
struct node{
    node* l = NULL,* r = NULL;
    int sum;
    node(node* l, node* r) : l(l), r(r){
        sum = (l ? l->sum : 0) + (r ? r->sum : 0);
    }
    node(int x) : sum(x){}
};
typedef node* pnode;
struct segTree{
    vector<pnode> root;
    int maxN;
    segTree(int n) : maxN(n){
        root.push_back(build(0, n));
    }
    pnode build(int l, int r){
        if(l == r-1) return new node(0);
        return new node(build(l, (l+r)/2), build((l+r)/2, r));
    }
    pnode update(pnode t, int poz, int c, int l, int r){
        if(l == r-1) return new node(t->sum + c);
        int m = (l+r)/2;
        if(poz < m) return new node(update(t->l, poz, c, l, m), t->r);
        return new node(t->l, update(t->r, poz, c, m, r));
    }
    void update(int poz, int c){
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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