Levko and Array Recovery masalasi yechimi

#	User	Rating
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

#	User	Contrib.
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	Dominater069	154
8	awoo	154
10	luogu_official	150

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:
1. Birinchi turdagi amal bu: massivdagi indekslari L dan R gacha bo'lgan elementlarni D ga oshirish. ya'ni dasturlash tili bilan aytganda:

for(int i = L; i<=R; i++)
    a[i]+=D;

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

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

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
m -> massiv ustida bajarilgan amallar soni; 1<=m<=5000

Keyingi m qatorda quyidagi tartibda ma'lumotlar kiritiladi:
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
2. l -> chap chegara 1<=l<=n
3. r -> o'ng chegara 1<=r<=n
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
NO -> agar yechim bo'lmasa
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:

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.

for(int i = L; i<=R; i++)
    diff[i]+=D;

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:

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

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:

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

M -> bu yerda L — 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 — 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.

kod

#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)
    {
        cout<<"YES"<<endl;
        for(int i = 1; i<=n; i++)
            cout<<ans[i]<<" ";
    }
    else
    {
        cout<<"NO";
    }
}

Comments (7)

Write comment?

Muhammad_Rahimov

7 years ago, # |

+11

Auto comment: topic has been updated by Muhammad_Rahimov (previous revision, new revision, compare).

→ Reply

Qudrat_Ibadullayev

← Rev. 2 →

Kodingni Block degan narsani ichiga tashasang bo'ladi. Link, Picturelarni qatorida 3-chi turibdi. Shunda kodni o'zi taniydi.

"Ammo almashtirish davomida shu massiv elementi boshlang'ich holatda qancha siljiganinigam hisobga olamiz:" shu qismni aniqroq tushuntirishni iloji bormi?

7 years ago, # ^ |

← Rev. 6 →

topish kerak bolgan massivni a deb olsak 
a[i] + diff[i] (1<=i<=n)
massivning hozirgi(amallar bajarilgandan keyingi) holatini keltirib chiqaradi

iCoder01

Agar birinchi turdagi amal kelsa diff massivini yangilaymiz Yangilaymiz?? Nishatib? Agar ikkinchi turdagi element kelsa L — R oraliqda M kamida bir marta uchraydimi yo'qmi tekshiramiz Shu M 3 marta uchragan bo'lsa lekin bizardan asa shu bir xil M 4 marta so'ralsa nichik bo'ladi? Yoki vundin bo'lmasliqi aniqmi? Vuni ehtimolini go'rish shart amasmi?

Yangilaymiz dagani diff massivni l Dan r gacha d ga oshirib ketamiz. Kamida bir Marta uchrashi esa bizga shu maksimal l VA r oraliqda uchrashini tekshirish uchun kerak. Qancha Marta uchrashini ahamiyati yo'q. Masala shartida 4 yoki 5 VA hokazo Marta uchrasin degan shart yo'q

Muhammad_Rahimov's blog

Masala Tarjimasi:

Kiruvchi ma'lumotlar:

Chiquvchi ma'lumotlar:

Masala Yechimi: