// oooo
/*
har chi delet mikhad bebar ~
gitar o ba khodet nabar! ~
;Amoo_Hasan;
*/
#include<bits/stdc++.h>
//#pragma GCC optimize("O3,no-stack-protector,unroll-loops")
//#pragma GCC target("avx2,fma")
using namespace std;
typedef long long ll;
typedef long double ld;
#define Sz(x) int((x).size())
#define All(x) (x).begin(), (x).end()
#define wtf(x) cout<<#x <<" : " <<x <<endl
#define mak make_pair
//constexpr int PRI = 1000696969;
constexpr ll INF = 1e18, N = 5e5 + 10, MOD = 1e9 + 7, SQ = 350;
int n, q;
int x[N], y[N], sum[N];
int a[N], b[N], c[N];
int fen[N / SQ][N], cur[N];
int id[N], last[N];
int ans_t[N];
void compress() {
vector<int> vc;
for(int i = 0; i < n; i++) {
vc.push_back(x[i]), vc.push_back(x[i] + y[i]);
}
for(int i = 0; i < q; i++) {
vc.push_back(a[i]), vc.push_back(c[i]);
}
sort(All(vc));
for(int i = 0; i < n; i++) {
sum[i] = lower_bound(All(vc), x[i] + y[i]) - vc.begin();
x[i] = lower_bound(All(vc), x[i]) - vc.begin();
}
for(int i = 0; i < q; i++) {
a[i] = lower_bound(All(vc), a[i]) - vc.begin();
c[i] = lower_bound(All(vc), c[i]) - vc.begin();
}
vector<pair<int, int> > block, b2;
for(int i = 0; i < n; i++) block.push_back({x[i], i});
for(int i = 0; i < q; i++) b2.push_back({a[i], i});
sort(All(block)), sort(All(b2));
for(int i = n - 1; i >= 0; i--) {
id[block[i].second] = i;
while(!b2.empty() && b2.back().first > block[i].first) {
last[b2.back().first] = i + 1;
b2.pop_back();
}
}
while(!b2.empty()) {
last[b2.back().first] = 0;
b2.pop_back();
}
}
bool cmp(pair<int, int> i, pair<int, int> j) {
int cnt1 = 0, cnt2 = 0;
if(i.second == 0) cnt1 = y[i.first];
else cnt1 = b[i.first];
if(j.second == 0) cnt2 = y[j.first];
else cnt2 = b[j.first];
if(cnt1 != cnt2) return cnt1 > cnt2;
return i.second < j.second;
}
void add_fen(int ind, int pos) {
for(++pos; pos; pos -= (pos & -pos))
fen[ind][pos]++;
}
int get_fen(int ind, int pos) {
int ans = 0;
for(++pos; pos < N; pos += (pos & -pos))
ans += fen[ind][pos];
return ans;
}
void add(int pos, int val) {
cur[pos] = val;
add_fen(pos / SQ, val);
}
int solve(int pos, int val) {
int ans = 0;
for(int i = pos; i / SQ == pos / SQ; i++) {
if(cur[i] >= val) ans++;
}
for(int i = pos / SQ + 1; i <= (n - 1) / SQ; i++) {
ans += get_fen(i, val);
}
return ans;
}
int main() {
ios :: sync_with_stdio(0), cin.tie(0); cout.tie(0);
cin >>n >>q;
for(int i = 0; i < n; i++) cin >>x[i] >>y[i];
for(int i = 0; i < q; i++) cin >>a[i] >>b[i] >>c[i];
compress();
vector<pair<int, int> > pos;
for(int i = 0; i < n; i++) {
pos.push_back(mak(i, 0));
}
for(int i = 0; i < q; i++) {
pos.push_back(mak(i, 1));
}
sort(All(pos), cmp);
memset(cur, -1, sizeof(cur));
for(auto j : pos) {
//cout<<j.first <<' ' <<j.second <<' ';
//if(j.second == 0) cout<<sum[j.first] <<endl;
//else cout<<c[j.first] <<endl;
/*if(j.second == 0) {
cout<<"^^" <<j.first <<' ' <<id[j.first] <<' ' <<sum[j.first] <<endl;
} else {
cout<<"***" <<j.first <<' ' <<last[a[j.first]] <<' ' <<c[j.first] <<endl;
}*/
if(j.second == 0) {
add(id[j.first], sum[j.first]);
continue;
}
ans_t[j.first] = solve(last[a[j.first]], c[j.first]);
}
for(int j = 0; j < q; j++)
cout<<ans_t[j] <<endl;
return 0;
}
Compilation message
/tmp/cchi39XK.o: in function `cmp(std::pair<int, int>, std::pair<int, int>)':
examination.cpp:(.text+0x1c): relocation truncated to fit: R_X86_64_PC32 against symbol `y' defined in .bss section in /tmp/cchi39XK.o
examination.cpp:(.text+0x2d): relocation truncated to fit: R_X86_64_PC32 against symbol `y' defined in .bss section in /tmp/cchi39XK.o
examination.cpp:(.text+0x43): relocation truncated to fit: R_X86_64_PC32 against symbol `b' defined in .bss section in /tmp/cchi39XK.o
examination.cpp:(.text+0x54): relocation truncated to fit: R_X86_64_PC32 against symbol `b' defined in .bss section in /tmp/cchi39XK.o
/tmp/cchi39XK.o: in function `solve(int, int)':
examination.cpp:(.text+0xa49): relocation truncated to fit: R_X86_64_PC32 against symbol `n' defined in .bss section in /tmp/cchi39XK.o
/tmp/cchi39XK.o: in function `compress()':
examination.cpp:(.text+0xaf3): relocation truncated to fit: R_X86_64_PC32 against symbol `n' defined in .bss section in /tmp/cchi39XK.o
examination.cpp:(.text+0xb2e): relocation truncated to fit: R_X86_64_PC32 against symbol `x' defined in .bss section in /tmp/cchi39XK.o
examination.cpp:(.text+0xb3b): relocation truncated to fit: R_X86_64_PC32 against symbol `y' defined in .bss section in /tmp/cchi39XK.o
examination.cpp:(.text+0xb79): relocation truncated to fit: R_X86_64_PC32 against symbol `n' defined in .bss section in /tmp/cchi39XK.o
examination.cpp:(.text+0xbcc): relocation truncated to fit: R_X86_64_PC32 against symbol `n' defined in .bss section in /tmp/cchi39XK.o
examination.cpp:(.text+0xbe2): additional relocation overflows omitted from the output
/usr/bin/ld: failed to convert GOTPCREL relocation; relink with --no-relax
collect2: error: ld returned 1 exit status
