Levko and Array Recovery masalasi yechimi
Difference between en16 and en17, changed 0 character(s)
### Masala Tarjimasi:↵
Levko massivlar bilan o'ynashni yaxshi ko'rar ekan. Unda a1, a2, a3 ... an ko'rinishidagi massiv bor ekan. U massiv bilan o'ynash davomida, shu massiv ustida 2 xil amal bajarar ekan.↵

Bu amallar:<br>↵
1. Birinchi turdagi amal bu: massivdagi indekslari L dan R gacha bo'lgan elementlarni D ga oshirish. ya'ni dasturlash tili bilan aytganda:↵

<pre>↵
for(int i = L; i<=R; i++)↵
    a[i]+=D;↵
</pre>↵

2. Ikkinchi turdagi amal: massivdagi indekslari L dan R gacha bo'lgan elementlar ichidan maksimalini topish.↵

<pre>↵
for(int i = L; i<=R; i++)↵
   mx = max(mx, a[i]);↵
</pre>↵

Levko sevimli massivini yo'qotib qo'yibdi shuning uchun u sizdan yordam so'rayapdi. Unda faqat massiv ustida bajarilgan amallar ro'yhati bor holos. Levkoga massivni tiklashda yordam bering.↵

#### Kiruvchi ma'lumotlar:↵
Birinchi bo'lib bizga n va m ketma ket kiritiladi.↵

n -> massiv elementlari soni; 1<=n<=5000<br>↵
m -> massiv ustida bajarilgan amallar soni; 1<=m<=5000<br>↵

Keyingi m qatorda quyidagi tartibda ma'lumotlar kiritiladi:<br>↵
1. t -> bajarilgan operatsiya tipi. Agar t = 1 bo'lsa u holda birinchi turdagi amal bajarilgan(qo'shish), agar t = 2 bo'lsa ikkinchi turdagi amal bajarilgan(maksimal topish). 1<=t<=2<br>↵
2. l -> chap chegara  1<=l<=n<br>↵
3. r -> o'ng chegara  1<=r<=n<br>↵
4. d yoki m -> bajarilayotgan amal turiga qarap, agar birinchi turdagi amal bo'lsa qo'shilayotgan son, agar ikkinchi turdagi amal bo'lsa topilgan maksimal son.↵

#### Chiquvchi ma'lumotlar:↵
YES -> agar yechim bo'lsa<br>↵
NO -> agar yechim bo'lmasa<br>↵
Agar yechim bo'lsa YES yozuvi ostida massiv elementlari chiqarilsin. Massiv elementlari modul jihatda 1e9 dan oshmaydi. ↵
|ai|<=1e9↵

O'zlaringizda g'oya chiqarib ishlashga urinib ko'ringlar!!! Agar bo'lmasa quyidagi yechimda foydalaninglar.↵

#### Masala Yechimi:↵

<spoiler summary="yechimi">↵
Bu masala yechimida asosoy ro'lni massiv ustida bajarilayotgan amallar o'ynaydi. Birinchi amaldan boshlasak. Birinchi amal haqidagi ma'lumotlardan quyidagicha foydalanamiz: diff nomli massiv olamiz (diff -> difference -> farq) va birinchi amal haqida ma'lumot kelganda diff massivini quyidagi tarzda o'zgartiramiz.↵

<pre>↵
for(int i = L; i<=R; i++)↵
    diff[i]+=D;↵
</pre>↵

Bu kodni bajarish orqali biz diff massivda hozirgi holatdagi massiv boshlang'ich massiv elementlaridan qanchaga farq etishini saqlab qo'yamiz. Masalan hozirda diff[2] = 4 bo'lsa demak a massivning 2 elementi boshlang'ich holatda 4 ga katta.↵

Endi ikkinchi turdagi amallarni ko'rib chiqsak. Bu amallarni qayta ishlash murakkabroq va bu amallar yordamida biz qidirilayotgan massivni hosil qilib olishimiz mumkin. Bu amallarni qayta ishlash uchun bizga javob massivni saqlab qo'yuvchi massiv kerak bo'ladi. Bu massivni ans deb nomlaymiz (ans -> answer -> javob) va uni masala shartidagi massiv elemntlaringing maksimal qiymati bilan to'ldiramiz ya'ni:↵

<pre>↵
for(int i = 0; i<=5000; i++){↵
    ans[i] = 1e9;↵
}↵
</pre>↵

Massivning bu holatda turishi bizga keyingi operatsiyalarda kerak bo'ladi. Endi eng qiziqarli qismi. Agar bizga ikkinchi turdagi amal berilsa, L -> R oraliqdagi faqatgina topilgan maksimal elementdan katta bo'lganlarini, shu topilgan maksimal bilan almashtiramiz. Ammo almashtirish davomida shu massiv elementi boshlang'ich holatda qancha siljiganinigam hisobga olamiz:↵

<pre>↵
for(int i = L; i<=R; i++)↵
    ans[i] = min(ans[i], M - diff[i]);↵
</pre>↵

M -> bu yerda L &mdash; R oraliqda topilgan maksimal.↵

Shu tarzda barcha amallarni qayta ishlab chiqsak biz natijaviy massivni qo'lga kiritamiz. Ammo bu hali javob degani emas. Biz bu massivni to'g'ri hosil qilinganligiga ishonch hosil qilishimiz kerak. Massivni tekshirish uchun biz diff massivni tozalatmiz ya'ni nollar bilan to'ldiramiz va ok nomli mantiqiy o'zgaruvchi hosil qilamiz. Keyinchalik amallardan yana bir marta o'tib chiqamiz. Agar birinchi turdagi amal kelsa diff massivini yangilaymiz. Agar ikkinchi turdagi element kelsa L &mdash; R oraliqda M kamida bir marta uchraydimi yo'qmi tekshiramiz akar bu element uchramay qolsa demak javob NO. Agar barcha M lar uchrasa YES javobini chiqaramiz va massivni chiqaramiz.↵

Shu yechimdan foydalanib kodni o'zingiz yozishga urinib ko'ring. Agar o'xshamasa quyidagi ko'dni o'rganib chiqishingiz mumkin.↵

<spoiler summary="kod">↵

<pre>↵
#include"bits/stdc++.h"↵
using namespace std;↵
const int N = 5001;↵
int diff[N], ans[N], t[N], l[N], r[N], d[N];↵
int main()↵
{↵
    for(int i = 0; i<N; i++)↵
        ans[i] = 1e9;↵
    int n,m;↵
    cin>>n>>m;↵
    for(int i = 0; i<m; i++)↵
    {↵
        cin>>t[i]>>l[i]>>r[i]>>d[i];↵
        if(t[i] == 1)↵
        {↵
            for(int j = l[i]; j<=r[i]; j++)↵
                diff[j]+=d[i];↵
        }↵
        else↵
        {↵
            for(int j = l[i]; j<=r[i]; j++)↵
                ans[j] = min(ans[j], d[i] - diff[j]);↵
        }↵
    }↵
    for(int i = 0; i<N; i++)↵
        diff[i] = 0;↵
    bool ok = 1;↵
    for(int i = 0; i<m && ok; i++)↵
    {↵
        if(t[i] == 1)↵
        {↵
            for(int j = l[i]; j<=r[i]; j++)↵
                diff[j]+=d[i];↵

        }↵
        else↵
        {↵
            ok = 0;↵
            for(int j = l[i]; j <= r[i]; j++)↵
                if(ans[j] + diff[j] == d[i])↵
                {↵
                    ok = 1;↵
                    break;↵
                }↵
        }↵
    }↵
    if(ok)↵
    {↵
        puts("YES/n");↵
        for(int i = 1; i<=n; i++)↵
            printf("%d/n",ans[i]);↵
    }↵
    else↵
    {↵
        puts("NO");↵
    }↵
}↵
</pre>↵
</spoiler>↵

cout codeforcesda yaxshi go'sanmin duripdi shuning uchun puts va printf ishlatisha majbur bo'ldim.↵

</spoiler>↵

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en19 English Muhammad_Rahimov 2017-07-28 17:51:26 0 (published)
en18 English Muhammad_Rahimov 2017-07-28 17:51:11 207 (saved to drafts)
en17 English Muhammad_Rahimov 2017-07-28 17:31:12 0 (published)
en16 English Muhammad_Rahimov 2017-07-28 17:30:41 102
en15 English Muhammad_Rahimov 2017-07-28 17:29:41 90 Tiny change: '"<<endl;\n ' -> '"<<endl;\n\n '
en14 English Muhammad_Rahimov 2017-07-28 17:25:03 1118
en13 English Muhammad_Rahimov 2017-07-28 17:21:36 140
en12 English Muhammad_Rahimov 2017-07-28 17:18:07 10 Tiny change: 'od">\n\n</kod>\n\n</spo' -> 'od">\n\n</spoiler>\n\n</spo'
en11 English Muhammad_Rahimov 2017-07-28 17:17:25 1204
en10 English Muhammad_Rahimov 2017-07-28 16:43:42 642
en9 English Muhammad_Rahimov 2017-07-28 16:33:38 556
en8 English Muhammad_Rahimov 2017-07-28 16:29:02 254
en7 English Muhammad_Rahimov 2017-07-28 16:26:45 32
en6 English Muhammad_Rahimov 2017-07-28 16:26:04 381
en5 English Muhammad_Rahimov 2017-07-28 16:23:10 156
en4 English Muhammad_Rahimov 2017-07-28 16:01:28 2 Tiny change: 'ytganda:\n<pre>\n<' -> 'ytganda:\n\n<pre>\n<'
en3 English Muhammad_Rahimov 2017-07-28 15:59:10 141 Tiny change: ' aytganda:<br>\n<pre>\n<' -> ' aytganda:\n<pre>\n<'
en2 English Muhammad_Rahimov 2017-07-28 15:54:16 1009
en1 English Muhammad_Rahimov 2017-07-28 15:43:47 691 Initial revision (saved to drafts)