A data structure problem ?
Разница между en8 и en9, 0 символ(ов) изменены
Given a constant $s$, an array of $n$ non-negative integers and you have to process $q$ queries of following types : ↵
↵
1. $l \ r \ b$ : for each $i$ in range $[l, r]$, if $a[i] < b$ let $a[i] = s - a[i]$↵
2. $l \ r \ b$ : for each $i$ in range $[l, r]$, if $a[i] > b$ let $a[i] = s - a[i]$↵
3. $i$ : return the current value of $a[i]$ ↵
↵
$1 \leq n, q \leq 5.10^5$↵
$1 \leq s, b \leq 10^7$↵
↵
Time limit : 2.5s↵
Memory limit : 512 mb↵
↵
I'm trying to solve the easier problem when all the updates appear before the queries, but I still can't;↵
I don't have any approach for this problem yet, can anyone give me some hints or something ?↵
Sorry for bad English :( ↵
Thanks :)

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en9 Английский I_Love_AnhThu 2024-08-24 14:00:58 0 (published)
en8 Английский I_Love_AnhThu 2024-08-24 14:00:43 3 Tiny change: 'n$1 \leq s \leq 10^7' -> 'n$1 \leq s, b \leq 10^7'
en7 Английский I_Love_AnhThu 2024-08-24 13:59:48 2 Tiny change: 't : 2.5s\n\nMemory l' -> 't : 2.5s\nMemory l'
en6 Английский I_Love_AnhThu 2024-08-24 13:59:37 4 Tiny change: 'eq 10^7$\nTime limit : 2.5s\nMemory l' -> 'eq 10^7$\n\nTime limit : 2.5s\n\nMemory l'
en5 Английский I_Love_AnhThu 2024-08-24 13:59:20 42 Tiny change: 'eq 10^7$\n\nI'm tr' -> 'eq 10^7$\nTime limit : 2.5s\nMemory limit : 512 mb\n\nI'm tr'
en4 Английский I_Love_AnhThu 2024-08-24 13:58:36 137
en3 Английский I_Love_AnhThu 2024-08-24 13:55:30 102
en2 Английский I_Love_AnhThu 2024-08-24 13:54:11 56 Tiny change: 'a[i]$ \n\n' -> 'a[i]$ \n\n$1 \leq n, q \leq 5.10^5$\n$1 \leq s \leq 10^7$\n$'
en1 Английский I_Love_AnhThu 2024-08-24 13:52:50 374 Initial revision (saved to drafts)