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 ?
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
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 ?
#include<bits/stdc++.h>
using namespace std;
int n,q,xi,ans;
pair<int,int> ar[200000];
int main() {
while(cin>>n) { for(int i=1;i<=n;i++) scanf("%d %d",&ar[i].first,&ar[i].second); sort(ar+1,ar+n+1); cin>>q; unordered_map<int,int> val; while(q--) { scanf("%d",&xi); if(val.count(xi)) { printf("%d\n",val[xi]); continue; } ans=0; int low=0,high=n+1; while(high-low>1) { int mid=(high+low)>>1; if(ar[mid].first>xi) high=mid; else low=mid; } for(int i=1;i<high;i++) if(ar[i].second >= xi) ans++; printf("%d\n",ans); val[xi]=ans; } } return 0;
}
#include<bits/stdc++.h>
using namespace std;
#define debug(...) printf( VA_ARGS )
//#define debug(...) /****nothing****/
#define pb push_back
#define mp make_pair
#define LL long long
int n,q,xi,ans;
pair<int,int> ar[200000];
int main()
{
while(cin>>n) { vector<pair<int,int> > vct; for(int i=1;i<=n;i++) { scanf("%d %d",&ar[i].first,&ar[i].second) ; vct.push_back(make_pair(ar[i].first,1)) ; vct.push_back(make_pair(ar[i].second+1,-1)) ; } sort(vct.begin(),vct.end()); int cnt=0; map<int,int> val; for(int i=0;i<vct.size();i++) { cnt+=vct[i].second; val[vct[i].first]=cnt; } cin>>q; while(q--) { scanf("%d",&xi); map<int,int>::iterator it=val.upper_bound(xi); it--; printf("%d\n",it->second); } } return 0;
}
I used the technique which has been used in this problem ( Two Tv's http://codeforces.net/problemset/problem/845/C )
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 :
#include<bits/stdc++.h>
using namespace std;
int tc,n,ar[123456],i,j,k,cas;
int main()
{
cin>>tc; for(cas=1; cas<=tc; cas++) { unordered_map<int,int> mxindex; scanf("%d",&n); for(i=1; i<=n; i++) scanf("%d",&ar[i]); for(j=n; j>=1; j--) if(mxindex.count(ar[j])==0) mxindex[ar[j]]=j; long long ans=0; for(i=1; i<=n; i++) for(int j=i+1; j<=n; j++) if(mxindex.count(ar[i]+ar[j])) { if(j+1<=mxindex[ar[i]+ar[j]]) ans++; } cout<<ans<<'\n'; } return 0;
}
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 .
#include<bits/stdc++.h>
using namespace std;
//#define debug(...) printf( VA_ARGS )
#define debug(...) /****nothing****/
#define pb push_back
#define mp make_pair
#define mem(ar,val) memset(ar,val,sizeof(ar))
int ar[5007],frq[10007][5007],n;
int main() {
while(cin>>n) { mem(frq,0); for(int i=1; i<=n; i++) { scanf("%d",&ar[i]); frq[ar[i]][i]=1; } for(int i=0; i<=10000; i++) for(int j=1; j<=n; j++) frq[i][j]+=frq[i][j-1]; sort(ar+1,ar+n+1); long long ans=0; for(int i=1; i<=n; i++) for(int j=i+1; j<=n; j++) { int sum=ar[i]+ar[j]; ans+=frq[sum][n]-frq[sum][j]; } cout<<ans<<endl; } return 0;
}
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/
Name |
---|