#include <bits/stdc++.h>
#define int long long
using namespace std;
int h[100], g[100];
vector<int> adj[100];
vector<int> th[100];
pair<int, int> a[100];
int n, k;
vector<int> cac;
int nodecnt=0;
int bit[1100005];
multiset<int> s;
int ans=0;
int putin[100005];
unordered_map<int, int> pos;
void update(int pos)
{
while(pos<=nodecnt)
{
bit[pos]++;
pos+=pos&-pos;
}
}
int get(int pos)
{
int ans=0;
while(pos>=1)
{
ans+=bit[pos];
pos-=pos&-pos;
}
return ans;
}
void dfs(int node)
{
for(auto i:adj[node])
{
for(auto j:th[node])
{
th[i].push_back(j+g[i]);
}
}
}
signed main()
{
cin>>n>>k;
for(int i=1; i<=n; i++)
{
cin>>h[i]>>g[i];
a[i].first=h[i];
a[i].second=i;
}
for(int i=1; i<=n/2; i++)
{
for(int j=i+1; j<=n/2; j++)
{
if(h[j]>=h[i])
{
adj[i].push_back(j);
}
}
}
for(int i=n; i>=n/2+1; i--)
{
for(int j=i-1; j>=n/2+1; j--)
{
if(h[j]<=h[i])
{
adj[i].push_back(j);
}
}
}
for(int i=1; i<=n/2; i++)
{
th[i].push_back(g[i]);
dfs(i);
}
for(int i=n; i>=n/2+1; i--)
{
th[i].push_back(g[i]);
dfs(i);
}
sort(a+1, a+n/2+1);
sort(a+n/2+1, a+n+1);
int itj=n;
cac.push_back(-1);
cac.push_back(0);
for(int i=n; i>=n/2+1; i--)
{
for(auto j:th[i])
{
cac.push_back(j);
}
}
cac.push_back(1000000000000);
sort(cac.begin(), cac.end());
for(int i=1; i<cac.size(); i++)
{
if(cac[i]!=cac[i-1])
{
nodecnt++;
pos[cac[i]]=nodecnt;
}
}
// update(1);
// for(int i=1; i<=n/2; i++)
// {
// for(auto j:th[i])
// {
// cout<<j<<" ";
// }
// cout<<endl;
// }
int takens=0;
takens++;
update(1);
for(int i=n/2; i>=1; i--)
{
while(a[itj].first>=a[i].first&&itj>=n/2+1)
{
// cout<<a[i].second<<" "<<a[itj].second<<endl;
for(auto j:th[a[itj].second])
{
update(pos[j]);
takens++;
}
itj--;
}
for(auto j:th[a[i].second])
{
// if(j>=k) ans++;
int concac=*lower_bound(cac.begin(), cac.end(),max(k-j,0ll));
// cout<<concac<<" "<<j<<" "<<max(pos[concac]-1, 0ll)<<" "<<takens<<endl;
ans+=takens-get(pos[concac]-1);
}
}
int concac=*lower_bound(cac.begin(), cac.end(), k);
ans+=takens-get(pos[concac]-1);
cout<<ans;
}
Compilation message
san.cpp: In function 'int main()':
san.cpp:102:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=1; i<cac.size(); i++)
~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
31 ms |
5132 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
640 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
103 ms |
9736 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
1152 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
737 ms |
39312 KB |
Output is correct |
| 2 |
Correct |
22 ms |
3468 KB |
Output is correct |
