Apologize to everyone for off topic
Hello evryone i tried many times to add image in a blog post or comment . When i click ctrl+p codeforces want a url of the image which i want to upload , but how can i upload an image from my desktop folder ?
Apologize to everyone for off topic
Hello evryone i tried many times to add image in a blog post or comment . When i click ctrl+p codeforces want a url of the image which i want to upload , but how can i upload an image from my desktop folder ?
UPDATE : I got a Qlog2(N) solution
Given a number N . then N lines follows some segment L[i] R[i] , where L[i] = left side of segment , R[i]= right side of segment
N
L1 R1
L2 R2
. . . . . .
LN RN
Then Given Q queries . Then Q lines as follows .
Q
X1
X2
X3 .
.
XQ
For each query you have to answer how many Segment are including the value Xi ( X >= L[i] && X <= R[i] )
Constraint :
1<=N<=10^5
0<=Li , Ri <= 10^9
1<=Q<=10^5
0<=Xi<=10^9
Sample input:
4
1 6
3 7
5 9
6 9
1
8
Sample output:
2
Explanation : 3rd segment 5-9 , 4th segment 6-9 both including 8 . Because : 8>=5 && 8<=9 , 8>=6 && 8<=9 . So ans is 2 .
How to solve it efficiently ?
I found a similar type of problem as last csacademy problem Sum of Triplets but slightly different :
Here they said find triplets such as A[i] + A[j] = A[k] where i<j<k . 1 <= Array size is <= 10^5 . 1 <= Array values < 2^16 .
Time limit : 12 second .
problem link : https://toph.co/p/counting-triplets
How to solve this problem without n^2 loop ? I am getting TLE .
My solution :
Since they said "A[i] + A[j] = A[k] where i<j<k " so i can not sort the data . I have to work as the given input .
At first I declare a map<int,int> mxIndex ; Then i store the maximum index of each data in this map .
Then I run a n^2 loop for every A[i] + A[j] , i search this sum in map . If found then i check the maximum index of A[i] + A[j] . If that index >= j+1 . That means found a triplet i < j < k so , ans++ . I know i will get WA . But i am getting TLE for n^2 loop . How can i do it efficiently ?
I am getting Wrong answer . Please help .
My logic is :
first sort the array , then run a n^2 for loop . For every ar[i]+ar[j] , i find out the frequency of ar[i]+ar[j] from index j+1 to n in array ar[] . Then i add this frequency to the answer .
To evaluate "frequency of ar[i]+ar[j] from index j+1 to n in array ar[] " i precalculated frq[X][Y] = "frequency of value X , from index 1 to Y " . For instance frq[5][2] means frequency of 5 from index 1 to 2 in arayy ar[] . I did it as like as partial sum technique .
So for every ar[i] + ar[j] I add this => sum=ar[i]+ar[j] ; ans += frq[sum][n] — frq[sum][j] ;
frq[sum][n] — frq[sum][j] means frequency from (j+1) to n = frequency(from 1 to n ) — frequency(from 1 to j ) ;
whats wrong in my logic or code ?
Problem link : https://csacademy.com/contest/archive/task/sum-triplets/