I think I overkilled this question by using Segment Trees . Although this approach is better than the Segment Tree one…
That’s not the link to your code. It’s just a link to the Codechef IDE. Paste a link of your submitted solution or something like that.
I was getting TLE with this code in 2nd subtask of Div2 C problem please tell what is wrong.
Why I am getting TLE for second task even if my logic is same.
code link: Solution
#include <iostream>
using namespace std;
int main() {
int t;
cin>>t;
while(t-- >0)
{
int n,q;
cin>>n;
cin>>q;
int a[n];
int x[q];
int y[q];
for(int i =0;i <n;i++)
{
cin>>a[i];
}
for(int i =0;i<q;i++)
{
cin>>x[i];
cin>>y[i];
}
int max=0;
int prev=-1;
for(int j=0;j<n;j++)
{
if(a[j]!=prev)
{
prev=a[j];
max++;
}
}
for(int i=0;i<q;i++)
{
if(a[x[i]-1]==y[i])
{
cout<<max<<endl;
continue;
}
else
{
if(x[i]-1!=0)
{
if(a[x[i]-1]==a[x[i]-2])
max++;
if(y[i]==a[x[i]-2])
max--;
}
if(x[i]-1!=n-1)
{
if(a[x[i]-1]==a[x[i]])
max++;
if(y[i]==a[x[i]])
max--;
}
a[x[i]-1]=y[i];
cout<<max<<endl;
}
}
}
return 0;
}
Even Tried with java fastIO
class chefweds {
static class FastReader
{
BufferedReader br;
StringTokenizer st;
public FastReader()
{
br = new BufferedReader(new
InputStreamReader(System.in));
}
String next()
{
while (st == null || !st.hasMoreElements())
{
try
{
st = new StringTokenizer(br.readLine());
}
catch (IOException e)
{
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt()
{
return Integer.parseInt(next());
}
long nextLong()
{
return Long.parseLong(next());
}
double nextDouble()
{
return Double.parseDouble(next());
}
String nextLine()
{
String str = "";
try
{
str = br.readLine();
}
catch (IOException e)
{
e.printStackTrace();
}
return str;
}
}
public static void main(String[] args) {
FastReader sc=new FastReader();
int t=sc.nextInt();
while(t-- >0)
{
int n=sc.nextInt();
int q=sc.nextInt();
int a[]=new int[n];
int x[]=new int[q];
int y[]=new int[q];
for(int i =0;i <n;i++)
{
int cv;
cv=sc.nextInt();
a[i]=cv;
}
for(int i =0;i<q;i++)
{
x[i]=sc.nextInt();
y[i]=sc.nextInt();
}
deploytemp obj=new deploytemp();
obj.solve(n,q,a,x,y);
}
}
}
class deploytemp
{
public void solve(int n,int q,int a[],int x[],int y[])
{
int max=0;
int prev=-1;
for(int j=0;j<n;j++)
{
if(a[j]!=prev)
{
prev=a[j];
max++;
}
}
for(int i=0;i<q;i++)
{
if(a[x[i]-1]==y[i])
{
System.out.println(max);
continue;
}
if(x[i]-1!=0)
{
if(a[x[i]-1]==a[x[i]-2])
max++;
if(y[i]==a[x[i]-2])
max--;
}
if(x[i]-1!=n-1)
{
if(a[x[i]-1]==a[x[i]])
max++;
if(y[i]==a[x[i]])
max--;
}
a[x[i]-1]=y[i];
System.out.println(max);
}
}
}
Try Fast Input/Output
I have heard that endl takes a lot of time as it flushes the output. Try using “\n” instead.
can anyone help me in my code i am not understanding why my list in second loop is not updating when i try to change the value in list it is not updating …
link for code - CodeChef: Practical coding for everyone
@earagav thanks for the help but actually i wasn’t using this line->
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using this sped up my output time to 1/10th
Thank you so much. It worked.
Please provide your code.
Thanks Sir.
very clean solution…
My solution
My approach is coming partially correct for the Subtask 2 Last Task. I am not able to get a test case which is not passing the task.
Would appreciate your help.
Thanks
Most Shortest Solution`
#include <bits/stdc++.h>
#define f(i,a,b) for(long long int i=a;i<b;i++)
using namespace std;
typedef long long int ll;
typedef vector vi;
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
ll t;cin>>t;
while(t–)
{
ll n,q;cin>>n>>q;
vi v(n+2,0);
f(i,1,n+1)cin>>v[i];
ll max_len=1;
f(i,2,n+1)
{
if(v[i]!=v[i-1])max_len++;
}
while(q–)
{
ll x,y;cin>>x>>y;
max_len -= v[x]!=v[x-1];
max_len -= v[x]!=v[x+1];
v[x]=y;
max_len += v[x]!=v[x-1];
max_len += v[x]!=v[x+1];
cout<<max_len<<endl;
}
}
return 0;
}
`
Hi, I find a mistake. You have given
if(x==0){
if(arr[x]==arr[x+1]) ans++;
else{
if(arr[x+1]==y) ans–;
}
}
Will this part run correctly if n=1 and x=1 as input?
Thanks for finding the mistake.
Refer this for more clarification