D - Cylinder || AtCoder Beginner Contest 247

 Link:  AtCoder Beginner Contest 247, D

প্রব্লেম স্টেইট্মেইন্টঃ দুই ধরনের কুয়েরি দেয়া হবে। যদি কুয়েরি ১ দেয়া হয় তাহলে সিলিন্ডারের ডান দিক থেকে সি সংখ্যক ভ্যালু প্রবেশ করানো হবে। অন্যথায় কুয়েরি ২ তে এসে সি সংখ্যক ভ্যালু ইরেজ করা হবে এবং ইরেজ করা সবগুলো ভ্যালুর যোগফল প্রিন্ট করে দিতে হবে।

অবসারবেশনঃ এক্স এবং সি এর ভ্যালু ১০*৯ পর্যন্ত হতে পারে। সুতরাং ব্রুটফুরস করে কিউ আকারে প্রব্লেম টা সল্ভ করা যাবে না । TLE দিবে।

সলিউশনঃ আমরা একটা ডিকিউ পেয়ার নিব। সি এর ভ্যালু জিরো না হওয়া পর্যন্ত ডিকিউ ইটারেট করব।সি এবং ডিকিউ তে থাকা অবশিষ্ট সংখ্যক ভ্যালুর মিনিমাম টা নিব। তারপর মিনিমাম টা ডিকিউ থেকে বাদ দিয়ে দিব। শেষে অবশিষ্ট ভ্যালু টা আবার ডিকিউ তে পুশ করে দিব।

CODE:

#include<bits/stdc++.h>

using namespace std;

#define ll long long

const ll N = 2e5 + 7;

int32_t main(){

ios_base::sync_with_stdio(false);cin.tie(NULL);

deque <pair<ll, ll> >DQ;

ll n; cin >> n;

ll x, c;

ll ind = 0, sum = 0;

for(ll i = 1; i <= n; ++i){

cin >> x;

if(x == 1){

cin >> x >> c;

DQ.push_back({x, c});

}

else{

sum = 0;

cin >> c;

while(c){

auto[val, num] = DQ.front();

DQ.pop_front();

ll MN = min(num, c);

sum += (MN*val);

c -= MN;

num -= MN;

if(num > 0) DQ.push_front({val, num});

}

cout << sum << '\n';

}

}

}

// 2 2 3 3 4 4 2 2