PROBLEM LINK:
Author: Akhilesh Yadav
Tester: Anand Raut
DIFFICULTY:
EASY
PREREQUISITES:
Math
PROBLEM:
Mohit(Ex GenSec ) is the most active member of the roasting club who loves giving tasks to other members. One day he observed that none of the members were paying attention to the online classes, so he decided to have some fun and overcome the boring lectures. He wrote N numbers on the virtual board (where the first number is 1, the last one is N and the ith number being i).
Then he asked M questions to every other member of the club. In each question, a number K was given by Mohit and the members had to give a single integer as an answer which will be the sum of all numbers present on the whiteboard.
There are some conditions that every member has to follow while answering.
- If K is already present on the whiteboard then swap the first and last number.
- Otherwise, replace the last number with K.
EXPLANATION:
Maintain 2 variables for the first and last element.
If m[i] is not in the given numbers replace the last element with the given M[i].
If m[i] is present in the given numbers, simply swap the first and last elements.
The k-sum clearly changes only in the first case and addition and subtraction just needs to be performed for inserted and deleted element respectively.
SOLUTIONS:
Setter's Solution
#include<bits/stdc++.h> using namespace std; typedef long long int ll; void solve(ll N, vector<ll> &op){ // current first & last number ll first=1,last=N; // to keep track of elements other than first and last ll minimum=1,maximum=N; // sum - maintain the current sum long long int sum=0; // sum of first N numbers sum = (N*(N+1))/2; // loop for m operations for(int i=0;i<(ll)op.size();i++){ if( op[i]==first || op[i]==last || (op[i]>minimum && op[i]<maximum) ){ swap(first,last) ; cout<<sum<<"\n"; } else{ sum = sum-last+op[i]; last=op[i]; cout<<sum<<"\n"; } } } int main(){ // n is for number present on board from 1 to N // m is number of operations ll n,m; cin>>n>>m; vector<ll>vec(m); for(int i=0;i<m;i++) cin>>vec[i]; solve(n,vec); }