#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#define ll long long
#define pb push_back
#define eb emplace_back
#define pu push
#define ins insert
#define lowbit(x) x&-x
#define bruh ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ff(x,a,b,c) for (auto x=a;x<=b;x+=c)
#define fd(x,a,b,c) for (auto x=a;x>=b;x-=c)
#define int ll
using namespace std;
const int N = 2e5+5;
const int mod = 1e9+7;
int power(int a,int b) {ll x = 1;if (a >= mod) a%=mod; while (b) {if (b & 1) x = x*a % mod;a = a*a % mod;b>>=1;}return x;}
map<int,int> cnt;
vector<array<int,4>> s;
int n,q;
int ans[N];
bool cmp(array<int,4> a,array<int,4> b)
{
return a[0]>b[0] || (a[0]==b[0] && a[3]<b[3]);
}
struct bintree{
vector<int> st;
vector<int> lazy;
void init()
{
st.resize(200005,0); lazy.resize(200005,0);
}
void update(int id,int val)
{
while (id<=cnt.size())
{
if (lazy[id]!=val) lazy[id] = val,st[id] = 0;
}
st[id]++;
id += lowbit(id);
}
int sum (int id,int x)
{
int ans = 0;
while (id>0)
{
if (lazy[id]!=x) lazy[id] = x,st[id] = 0;
ans+=st[id];
id-=lowbit(id);
}
return ans;
}
} bit;
void cdq(int id,int l,int r)
{
if (l==r) return;
int mid = l+(r-l)/2;
cdq(id*2,l,mid); cdq(id*2+1,mid+1,r);
int i = l,j = mid+1;
vector<array<int,4>> a;
while (i<=mid && j<=r)
{
if (s[i][1]>=s[j][1])
{
if (s[i][3]==-1) bit.update(cnt.size(),id);
a.pb(s[i]); i++;
} else
{
if (s[j][3]!=-1) ans[s[j][3]]+=bit.sum(cnt.size()-s[j][2],id);
a.pb(s[j]); j++;
}
}
while (i<=mid) a.pb(s[i]),i++;
while (j<=r)
{
if (s[j][3]!=-1) ans[s[j][3]]+=bit.sum(cnt.size()-s[j][2],id);
a.pb(s[j]); j++;
}
for (int i=l;i<=r;i++) swap(s[i],a[i-l]);
}
void solve()
{
bit.init();
cin>>n>>q;
for (int i=0;i<n;i++)
{
int x,y; cin>>x>>y;
s.pb({x,y,x+y,-1});
cnt[x+y] = 1;
}
for (int i=0;i<q;i++)
{
int x,y,z; cin>>x>>y>>z;
s.pb({x,y,z,i});
cnt[z]++;
}
sort(s.begin(),s.end(),cmp);
int idx = 0;
for (auto &[a,b] : cnt) b = idx++;
for (auto &[a,b,c,d] : s) c = cnt[c];
cdq(1,0,cnt.size()-1);
for (int i=0;i<q;i++) cout<<ans[i];
}
signed main()
{
bruh
int t = 1;
//cin>>t;
while (t--)
{
solve();
cout<<"\n";
}
}
Compilation message
examination.cpp: In member function 'void bintree::update(long long int, long long int)':
examination.cpp:41:12: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::map<long long int, long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
41 | while (id<=cnt.size())
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3020 ms |
3672 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3057 ms |
16576 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3057 ms |
16576 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3020 ms |
3672 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
