# AGCY - Editorial

Practice

Author: Vaishakh SM
Tester: Smit Mandavia
Editorialist: Vaishakh SM

Easy

# PREREQUISITES:

Knowledge of prefix sums

# PROBLEM:

Given an array, A of size N initially filled with 0's, for each query containing two integers L,R add 1 to A[L] , 2 to A[L+1]R-L+1 to A[R]. In general, add i+1 to A[L+i] for every L\leq i \leq R.

# QUICK EXPLANATION:

• In an array initially filled with 0's, use standard prefix sums to first add 1 to each L,R query, let this array be B.
• Subtract R-L+1 from A[R+1] for each query (store the queries beforehand)
• Take prefix sum of B and print B[1] to B[N]

# EXPLANATION:

Let us first try to solve a simpler question, how can we add 1 to each L,R query, we will later see how the original question is essentially the same as this simpler question.

For adding 1 to each L,R query, we first start with an array filled with 0's (say A), then we add 1 to each A[L] and subtract 1 from each A[R]. Then we take the prefix sum of A.

Now, observe that if we take the prefix sum of 1,1,1,-3, we get 1,2,3,0. Hence we have added 1,2,3 to A[0], A[1],A[2] respectively. Using this logic we can see that in general if we have M, 1's in an array followed by -M and if we take the prefix sum of the array we have added 1,2,... M to the first M indices of the array.

Hence, we will first add 1 in an initially empty array for each L,R query, then we will subtract R-L+1 from A[R+1] for each query and take prefix sum again to get the desired result.

## TIME COMPLEXITY

Time complexity is O(N + Q), where N is size of array and Q is number of queries for each testcase.

## SOLUTIONS

Setter's Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;

int main()
{
lli t,n,q,l,r;

cin>>t;

while(t--)
{
cin>>n>>q;

vector<lli> arr(n+3);

vector<pair<lli,lli>> Indices;

while(q--)
{
cin>>l>>r;

arr[l]++;
arr[r+1]--;
// Adding 1 to arr[l] and subtracting 1
// from arr[r+1] as mentioned in editorial

Indices.push_back({l,r+1});
}

for(int i =1;i<=n;i++)
{
arr[i]+=(arr[i-1]);
}
// Taking prefix sum to add 1 to each L,R query

for(auto x:Indices) arr[x.second]-=(x.second-x.first);
// After generating the array where the queries are increased with 1
// I am subtracting R-L+! to r+1th index

for(int i =1;i<=n;i++)
{
arr[i]+=(arr[i-1]);
}
// Taking prefix sum again

for(int i=1;i<=n;i++)cout<<arr[i]<<" ";
//Final output

cout<<endl;
}
}

Tester's Solution
    #include<bits/stdc++.h>
using namespace std;

#define ll long long int
#define FIO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define mod 1000000007

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();
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;
}
assert(l<=x && x<=r);
return x;
} else {
cerr << (int)g << "\n";
assert(false);
}
}
}
string ret="";
int cnt=0;
while(true){
char g=getchar();
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){
}
long long readIntLn(long long l,long long r){
}
}
}

int main()
{
FIO;
int t,n,q,k,i,j,sum_n,sum_q;

sum_n=0;
sum_q=0;
while(t--){
sum_n+=n;
sum_q+=q;
ll arr[n+3]={0};
while(q--){
arr[j]++;
arr[k+1]--;
arr[k+1]-=(k-j+1);
arr[k+2]+=(k-j+1);
}
for(i=1;i<=n;i++)
arr[i]+=arr[i-1];
for(i=1;i<=n;i++)
arr[i]+=arr[i-1];

for(i=1;i<=n;i++)
cout << arr[i] << " ";
cout << "\n";
}
assert(getchar()==-1);
assert(sum_n<=1000000);
assert(sum_q<=1000000);
return 0;
}

11 Likes

Can someone mention some problems like this one? I like the technique wanna solve more

1 Like

Wow, the solution seems so simple but at the same time feels hard to come up with it .

1 Like

I think these set of problems will be helpful for you.

1 Like

Can anybody tell me on which testcase my solution is giving WA?

#include<bits/stdc++.h>
using namespace std;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define fr(i,k) for(i=0;i<k;i++)
#define deb(x) cerr<<#x<<" = “<<x<<endl;
#define deb2(x,y) cerr<<#x<<” ="<<x<<endl<<#y<<" ="<<y<<endl;
#define SZ(x) (x).size();
#define ll long long
#define mod 1000000007
#define ff first
#define ss second
#define pb push_back
#define em emplace_back
#define ulli unsigned long long int
#define inf 1e18
#define endl “\n”
typedef vector<vector> vvll;
typedef vector vll;
typedef vector<pair<ll,ll>> vpll;
typedef pair<ll,ll> pll;
typedef vector vb;
void solve();

int main() {
fastio;
/#ifndef ONLINE_JUDGE
freopen(“input.txt”, “r”, stdin);
freopen(“output.txt”, “w”, stdout);
#endif
/

ll t;
t = 1;

cin >> t;
while (t--)
{
solve();
}
return 0;


}

inline void solve()
{
ll n,q,i,l,h,m;
cin>>n>>q;

vector<pair<ll,ll>> v(q);
vector<ll> ans(n+1,0);
vector<ll> pre(q+1,0);

for(i=0;i<q;i++)
{
cin>>v[i].first>>v[i].second;
}

sort(v.begin(),v.end());

pre[1] = v[0].first;
for(i=2;i<=q;i++)
pre[i]+=(pre[i-1]+v[i-1].first);

for(i=1;i<=n;i++)
{
l=0;
h=q-1;
ll idx1=-1,idx2=-1;

while(l<=h)
{
m = l+(h-l)/2;

if(v[m].first>i)
{
h=m-1;
}
else
{
if(v[m].second>=i)
{
idx2=m;
l=m+1;
}
else
l=m+1;
}
}

l=0;
h=q-1;

while(l<=h)
{
m = l+(h-l)/2;

if(v[m].first>i)
{
h=m-1;
}
else
{
if(v[m].second>=i)
{
h=m-1;
idx1=m;
}
else
l=m+1;
}
}

if(idx1!=-1 && idx2!=-1)
{
ll b;
b = idx2-idx1+1;

ans[i] = (i+1)*b - (pre[idx2+1]-pre[idx1]);
}

}

for(i=1;i<=n;i++)
cout<<ans[i]<<" ";

cout<<endl;


}

Another Approach to solve just stimulate the process

https://www.codechef.com/viewsolution/40958260

How codechef can tag problems like this as easy

2 Likes

how this solution getting TLE(Solution: 41306165 | CodeChef) and this solution getting acc ans(Solution: 41306753 | CodeChef) … there are both same except in line 198…please can anyone tell me whats wrong here.