PROBLEM LINK:
Practice
Div-3 Contest
Div-2 Contest
Div-1 Contest
Setter: Aditya Kumar Singh
Tester: Daanish Mahajan
DIFFICULTY:
Easy
PREREQUISITES:
Multiset, Greedy
PROBLEM:
N district having some capacity of people given in the array. For each Q query, you are given two numbers X and P. P peoples are dropped at district X. Each dropped person moves forward to get shelter in the district. If someone unable to find a location will die. You have to find the total distance traveled by people who will get shelter.
EXPLANATION:
We can use a multiset of pairs to store all the districts with their capacity.
For each query: we can fill the nearest right district until they are not full and remove them once it got full and If some people are left to be accommodating and there is no vacant space on right they are going to die.
Even there are up to (10^9) people at each query the complexity will be under (NlogN+QlogN) always as the nearest right district will be either completely used and removed or remain and queries will continue.
SOLUTIONS:
Setter's Solution
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define is insert
#define rep1(i,a,b) for(long long i=a;i<=b;i++)
#define F first
#define S second
#define file ifstream fin("input.txt");ofstream fout("output.txt");
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fr(n) for(long long i=0;i<n;i++)
#define rep(i,a,b) for(long long i=a;i<b;i++)
#define ALL(x) (x).begin(), (x).end()
typedef long long int ll;
typedef long double ld;
typedef vector<ll> vi;
void solve()
{
ll n,a,q,k,x;
cin>>n;
set<pair<ll,ll> >se;
rep(i,1,n+1)
{
cin>>a;
se.is({i,a});
}
cin>>q;
fr(q)
{
ll dis=0,ini;
cin>>x>>k;
auto it=se.lower_bound({x,0});
while(it!=se.end() && k>0)
{
if(it->S>k)
{
dis+=(k*(it->F - x));
se.is({it->F,it->S - k});
se.erase(it);
k=0;
}
else
{
dis+=(it->S*(it->F-x));
k-=it->S;
auto itr=it;
it++;
se.erase(itr);
}
}
cout<<dis<<endl;
}
}
int32_t main()
{
#ifndef ONLINE_JUDGE
freopen("inputf.in", "r", stdin);
freopen("outputf.in", "w", stdout);
#endif
fast;
ll t=1;
// cin>>t;
while(t--)
solve();
return 0;
}
Tester's Solution
#include<bits/stdc++.h>
using namespace std;
# define ll long long int
# define pb push_back
# define pll pair<ll, ll>
# define pli pair<ll, int>
# define mp make_pair
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
// char g = getc(fp);
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
if(is_neg){
x= -x;
}
// cout << x << " " << l << " " << r << endl;
assert(l<=x && x<=r);
return x;
} else {
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
// char g=getc(fp);
assert(g != -1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
const int maxn = 1e5, maxq = 1e5, maxv = 1e9;
int main()
{
int n = readIntLn(1, maxn);
int cap[n + 1];
set<int> s;
for(int i = 1; i <= n; i++){
cap[i] = (i == n ? readIntLn(1, maxv) : readIntSp(1, maxv));
s.insert(i);
}
int q = readIntLn(1, maxq);
while(q--){
int x = readIntSp(1, n), k = readIntLn(1, maxv);
auto it = s.lower_bound(x);
ll ans = 0;
while(it != s.end() && k > 0){
int id = *it;
int rem = min(cap[id], k);
k -= rem; cap[id] -= rem;
ans += (ll)(id - x) * rem;
if(cap[id] == 0)s.erase(it);
it = s.lower_bound(x);
}
cout << ans << endl;
}
assert(getchar()==-1);
}
!