Levko and Array Recovery masalasi yechimi

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

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: