Big array of Dino#9639
Written by @Yusif_M
In this problem there are pairs of numbers first number of pair is showing how many times will the second number of pair be inserted. At the end of input there is a number and it is the index of the required number. If we insert numbers to array manually, it will hit time limit because n\le10^5 pairs and first number of each pair a_i\le10^5. It will have time complexity O(10^{10}) and it will absolutely hit time limit. Optimal method for this problem's solution is to make array and keep the counts of each element inside that array after that we'll begin to add counts to variable and if sum is equal or greater than k, which means we saw that element. Here is the code of implementation in C++:
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <bitset>
#include <string>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <unordered_set>
#define ll long long
#define ld long double
#define db double
#define ch char
#define sg string
#define st set
#define stck stack
#define pq priority_queue
#define dq deque
#define vc vector
#define bl bool
#define mp map
#define cp cout.precision
#define ts to_string
#define mst multiset
#define uost unordered_set
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
ll n,k,num1,num2,count=0,counts[100001];
scanf("%lld",&n);
memset(counts,0,sizeof(counts)); //set all counts to zero
for(int i=0;i<n;i++)
{
scanf("%lld %lld",&num1,&num2);
counts[num2]+=num1; //add the counts of the number to the index which is equal to number
}
scanf("%lld",&k);
for(int i=1;i<=100000;i++)
{
count+=counts[i]; //add them to count variable to keep track of k-th element
if(count>=k) //if it greater than k then it means we saw and passed the number which we are searching. If it is equal then we are exactly on the index k
{
printf("%lld",i); //output number
return 0;
}
}
}