Здесь представлены темы заключительного этапа Республиканской Олимпиады (Казахстан) по информатике. (просмотреть)
Олимпиада пройдет с 24 по 28 марта 2024 года в Алматы.
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 3947 |
2 | jiangly | 3734 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3612 |
7 | ecnerwala | 3581 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | ksun48 | 3479 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | awoo | 162 |
2 | maomao90 | 160 |
3 | nor | 156 |
4 | cry | 155 |
4 | adamant | 155 |
4 | atcoder_official | 155 |
4 | -is-this-fft- | 155 |
8 | maroonrk | 153 |
9 | SecondThread | 147 |
10 | Petr | 146 |
Здесь представлены темы заключительного этапа Республиканской Олимпиады (Казахстан) по информатике. (просмотреть)
Олимпиада пройдет с 24 по 28 марта 2024 года в Алматы.
====== lvl 1 | basic knowledge =====
Introductory lesson
math (formulas, basic mathematic operations)
if/else
loop
string, array
asymptotics
sort (bubble, merge)
STL, map, set
======= lvl 2 | pre-intermediate =====
Two pointers
Binary Search/Ternary Search
prefix sum
sliding window
functions / recursion (prime)
Bruteforce
Greedy
scan line
permutation
========= lvl 3 | intermediate ===============
prime, factorization, number theory
dp basic
graph, dfs, bfs
Sieve
combinatorics
modular arith
Hash
========= lvl 4 | upper-intermediate ==========
fenwick tree
sqrt decomposition
Segment Tree
Sparse Table
TopSort
Eulerian cycle, path
Finding path algos
dsu, mst
bitmasks and dp bitmasks
Mo's Algo
digit dp
DP on substring
invariant, monovariant, dirichlet
======== lvl 5 | advanced ========
Cut vertices, edges
SCC
lca
Z algo/Prefix func
trie
meet in the middle
small to large
dp on trees
Inclusion-Exclusion, Probability
Expected val
segment tree lazys
======== lvl 6 | proficient ======
Nim
Persistent Data Structures
Maximum bi-partition (Kuhn's algo)
Matrixes
Author: bash
По условию задачи, есть 2 вида запросов:
1) Вывести количество элементов на отрезке $$$[l,r]$$$, то есть от позиции $$$l$$$ до позиции $$$r$$$ количество таких $$$a_i$$$, что $$$a_i$$$ $$$\ge$$$ $$$c$$$.
2) Поменять значение на позиции $$$pos$$$ на $$$val$$$.
Как будем хранить элементы массива?
Используем метод Sqrt-декомпозиции. Это такой метод (структура данных), которая позволяет нам работать над массивами большущих размеров. Итак, давайте разобьем массив на $$$k$$$ блоков длины $$$n/k$$$. Будем хранить $$$k$$$ векторных массивов, то есть
vector<int>b[k];
Далее, при инициализации элементов массива $$$a$$$, будем добавлять $$$a_i$$$ в блок с номером $$$b[i/k]$$$. Затем, после добавления всех элементов, отсортируем каждый блок по неубыванию. Массив $$$a$$$ должен быть нулевой индексации.
Отвечаем на запросы на готовом упрощенном массиве.
1-й вид запросов На тех блоках, которые полностью входят в наш отрезок $$$[a,b]$$$, мы будем просто делать бинарный поиск. И $$$(n/k)-cnt(good)$$$ будет ответом на один из блоков, где $$$cnt(good)$$$ — количество не подходящих нам чисел, то есть тех, которые меньше $$$c$$$. Если же блок полностью не входит в отрезок, мы там просто в лоб пройдемся от позиции $$$a$$$ до позиции $$$(l1+1)*k-1$$$, где это первая позиция, относящаяся самому первому блоку слева. Аналогично сделаем и справа, где блок стоит правее, чем конечная позиция последнего блока.
2-й вид запросов Для выполнения такого запроса мы просто поменяем значение сначала $$$b[block][i]$$$, которое равно числу, стоящему на позиции $$$pos$$$ в массиве $$$a$$$, на значение $$$val$$$. $$$block$$$ — это номер блока, в котором находится $$$a_{pos}$$$. Затем меняем само значение $$$a_{pos}$$$ , и сортируем изменившийся блок.
К тому же, значения позиций в запросах нужно отнять на 1, так как индексация в массиве начинается с нуля.
КОД:
#include <bits/stdc++.h>
using namespace std;
const long long maxn=5e5+1;
int n,q,a[maxn],k=400;
vector<int>b[maxn];
int main(){
cin>>n;
for(int i=0;i<n;i++){
cin>>a[i];
b[(i/k)].push_back(a[i]);
}
for(int i=0;i<(n/k);i++){
sort(b[i].begin(),b[i].end());
}
cin>>q;
while(q--){
int t;
cin>>t;
if(t==1){
int pos,val;
cin>>pos>>val;
pos--;
int bl=pos/k;
for(int i=0;i<b[bl].size();i++){
if(b[bl][i]==a[pos]){
b[bl][i]=val;
break;
}
}
a[pos]=val;
sort(b[bl].begin(),b[bl].end());
} else{
int l,r,val;
cin>>l>>r>>val;
l--,r--;
int b1=l/k,b2=r/k,res=0;
if(b1==b2){
for(int i=l;i<=r;i++){
if(a[i]>=val) res++;
}
}
else{
for(int i=b1+1;i<b2;i++){
int pos=lower_bound(b[i].begin(),b[i].end(),val)-b[i].begin();
res+=(b[i].size()-pos);
}
for(int i=l;i<=((b1+1)*k)-1;i++){
if(a[i]>=val) res++;
}
for(int i=b2*k;i<=r;i++){
if(a[i]>=val) res++;
}
}
cout<<res<<'\n';
}
}
}
Ислам Сипатталов ( каз. Ислам Даниярұлы Сипатталов, род. 28 сент. 2008, Актобе, Казахстан) — ученик Актюбинского областного специализированного лицея-интерната "Білім-Инновация" для одарённых юношей.
Краткая биография
Ислам родился 28 сентября 2008 (воскресенье) в обычной казахской семье. В 2011 году родители сдали его в детский садик, который был неподалёку от дома. В 2013 году он зачисляется в Городской Художественный Лицей города Актобе, в детскую группу. Первый звонок прозвенел для Ислама в сентябре 2015 года. Он учился в СШЛ №27 города Актобе. Затем, когда его любимая классная руководительница переехала в Россию, в классе началась делёжка, новый руководитель не пришёлся по душе родителям, участились скандалы. Незадолго после начала второго класса, Ислам переходит в СШГ №9 города Актобе. Там он проучился 5 лет. С 2017 по 2021 года ходил в лингвистический центр "DARINA", на английский язык. В апреле 2021 года он успешно сдал и прошел экзамен в БИЛ, а затем в конце мая в НИШ. Пред ним стал трудный выбор, но вскоре он решился пойти учиться в БИЛ. Творчеством Ислам занимается ещё с раннего детства. Как говорилось ранее, Ислам учится в Художественном Лицее города Актобе с 2013 года (11 лет). Он пошёл туда по инициативе мамы, будучи ещё в садике. До 5 класса учился в детской группе. Как правило, при переходе в 5-й класс общеобразовательной школы, он перешёл в 0-й класс в Художественном Лицее. Сейчас учится в 4-м классе, на заключительном этапе художественного образования.
Название |
---|