#include <bits/stdc++.h>
using namespace std;
// Miscellanous
#define gc getchar_unlocked
#define ll long long
#define ull unsigned long long
#define si(x) scanf("%d",&x)
#define si2(x,y) scanf("%d %d",&x,&y)
#define sl(x) scanf("%lld",&x)
#define sl2(x,y) scanf("%lld %lld",&x,&y)
#define sstr(s) cin >> s
#define pi(x) printf("%d\n",x)
#define pi2(x,y) printf("%d %d\n",x,y)
#define pl(x) printf("%lld\n",x)
#define pl2(x,y) printf("%lld %lld\n",x,y)
#define ps(s) cout << s << endl
#define py printf("YES\n")
#define pn printf("NO\n")
#define pnl printf("\n")
#define pb push_back
#define ff first
#define ss second
#define sz(v) (int)v.size()
#define all(v) v.begin(),v.end()
#define sortv(v) sort(all(v))
#define revsort(v) sort(v.rbegin(),v.rend())
#define reverse(v) reverse(all(v))
#define alla(arr,sz) arr,arr+sz
#define sorta(arr,sz) sort(alla(arr,sz))
#define reversea(arr,sz) reverse(alla(arr,sz))
#define cta(x,v) count(alla(arr,sz),x)
#define ct(x,v) count(all(v),x)
#define cto(v) count_if(all(v),[] (int a) {return a%2 == 1;})
#define cte(v) count_if(all(v),[] (int a) {return a%2 == 0;})
#define MAX(a,b) a = max(a,b)
#define MIN(a,b) a = min(a,b)
#define clr(x) memset(x, 0, sizeof(x))
// Loops
#define loop(i,s,e) for (int (i)=(s);(i)<(e);++(i))
#define loope(i,s,e) for (int (i)=(s);(i)<=(e);++(i))
#define forc(c,s,e) for (char (c)=(s);(c)<=(e);++(c))
#define forr(i,s,e) for (int (i)=(s);(i)>=(e);--(i))
#define foreach(val,cont) for (auto &(val) : (cont))
#define rep(i,n) loop(i,0,n)
#define repn(i,n) loope(i,1,n)
// Constants
#define PI 3.1415926535897932384626
#define sqr(x) ((x) * 1ll * (x))
const int mod = 1000000007;
// Containers
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<string,string> pss;
typedef map<int, int> mii;
// Input Output
#define takei(a) int a; si(a)
#define takei2(a,b) int a,b; si2(a,b)
#define takel(a) ll a; sl(a)
#define takel2(a,b) ll a,b; sl2(a,b)
#define takearri0(n,a) vi a(n); rep(i,n) si(a[i])
#define takearri1(n,a) vi a(n+1); a[0] = 0; repn(i,n) si(a[i])
#define takearrl0(n,a) vl a(n); rep(i,n) sl(a[i])
#define takearrl1(n,a) vl a(n+1); a[0] = 0ll; repn(i,n) sl(a[i])
// Debug
void _print(int t) {cerr << t;}
void _print(ll t) {cerr << t;}
void _print(string t) {cerr << t;}
void _print(char t) {cerr << t;}
void _print(double t) {cerr << t;}
void _print(ull t) {cerr << t;}
template <class T, class V> void _print(pair <T, V> p);
template <class T> void _print(vector <T> v);
template <class T> void _print(unordered_set <T> v);
template <class T> void _print(unordered_multiset <T> v);
template <class T> void _print(set <T> v);
template <class T> void _print(multiset <T> v);
template <class T, class V> void _print(unordered_map <T, V> v);
template <class T, class V> void _print(unordered_multimap <T, V> v);
template <class T, class V> void _print(map <T, V> v);
template <class T, class V> void _print(multimap <T, V> v);
template <class T, class V> void _print(pair <T, V> p) {cerr << "{"; _print(p.ff); cerr << ","; _print(p.ss); cerr << "}";}
template <class T> void _print(vector <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(unordered_set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(unordered_multiset <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(multiset <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void _print(unordered_map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void _print(unordered_multimap <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void _print(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void _print(multimap <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}
#ifndef ONLINE_JUDGE
#define deb(x) cerr << #x << " = "; _print(x); cerr << endl;
#else
#define deb(x)
#endif
inline string inttostr(ll a){
char x[100];
sprintf(x,"%lld",a); string s = x;
return s;
}
inline ll strtoint(string a){
char x[100]; ll res;
strcpy(x,a.c_str()); sscanf(x,"%lld",&res);
return res;
}
inline string getstr(void){
char x[1000005];
scanf("%s",x); string s = x;
return s;
}
inline string uppercase(string s){
int n = sz(s);
rep(i,n) if (s[i] >= 'a' && s[i] <= 'z') s[i] = s[i] - 'a' + 'A';
return s;
}
inline string lowercase(string s){
int n = sz(s);
rep(i,n) if (s[i] >= 'A' && s[i] <= 'Z') s[i] = s[i] - 'A' + 'a';
return s;
}
// ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
const int LOGN = 30;
const int MAXN = 1 << LOGN;
const int B_SIZE_SORT = 30000;
int ai,bi;
bool cmp(vl &a, vl &b)
{
ll ai = a[0]/B_SIZE_SORT , bi = b[0]/B_SIZE_SORT;
if(ai != bi) return ai < bi;
return (ai&1 ? a[1] < b[1] : a[1] > b[1]);
}
int f[100000 + 5];
const int B_SIZE = 300;
const int block_ct = 100000/B_SIZE + 5;
int block[block_ct];
vi d;
void add(vpii &v, int lb)
{
for (int i = sz(v) - 1; i >= 0; i--)
{
if(v[i].ff < lb) return;
int x = v[i].ss;
f[x]++;
block[x/B_SIZE]++;
}
}
void remove(vpii &v, int lb)
{
for (int i = sz(v) - 1; i >= 0; i--)
{
if(v[i].ff < lb) return;
int x = v[i].ss;
f[x]--;
block[x/B_SIZE]--;
}
}
int get(int k)
{
int ans = 0;
int curB = k/B_SIZE;
loop(i,k,(curB+1)*B_SIZE) ans += f[i];
loop(i,curB+1,block_ct) ans += block[i];
return ans;
}
int main()
{
clr(f); clr(block);
takei2(n,q);
d.resize(n);
map<int,vi> m1,m2;
rep(i,n)
{
takei2(s,t);
m1[s].pb(t);
m2[t].pb(s);
d[i] = s+t;
}
// Coordinate Compression
sortv(d);
d.resize(unique(all(d)) - d.begin());
vector<vpii> left; vi li;
for(auto &pr : m1)
{
vi &v = pr.ss;
vpii tmp;
sortv(v);
for(auto ele : v)
{
tmp.pb({ele , lower_bound(all(d) , ele+pr.ff) - d.begin()});
}
left.pb(tmp);
li.pb(pr.ff);
}
vector<vpii> right; vi ri;
for(auto &pr : m2)
{
vi &v = pr.ss;
vpii tmp;
sortv(v);
for(auto ele : v)
{
tmp.pb({ele , lower_bound(all(d) , ele+pr.ff) - d.begin()});
}
right.pb(tmp);
ri.pb(pr.ff);
}
vvl queries(q,vl(4));
rep(i,q)
{
takei2(l,r); takei(k);
queries[i][0] = l;
queries[i][1] = r;
queries[i][2] = i;
queries[i][3] = lower_bound(all(d) , k) - d.begin();
}
sort(all(queries) , cmp);
int pl = sz(li), pr = sz(ri);
vi ans(q);
rep(i,q)
{
int l = queries[i][0] , r = queries[i][1] , id = queries[i][2], k = queries[i][3];
while(pl > 0 and li[pl-1] >= l)
{
pl--;
if(pr < sz(ri)) add(left[pl] , ri[pr]);
}
while(pr > 0 and ri[pr-1] >= r)
{
pr--;
if(pl < sz(li)) add(right[pr] , li[pl]);
}
while(pl < sz(li) and li[pl] < l)
{
if(pr < sz(ri)) remove(left[pl] , ri[pr]);
pl++;
}
while(pr < sz(ri) and ri[pr] < r)
{
if(pl < sz(li)) remove(right[pr] , li[pl]);
pr++;
}
ans[id] = get(k);
}
for(auto i : ans) pi(i);
return 0;
}
// ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Compilation message
examination.cpp: In function 'std::string uppercase(std::string)':
examination.cpp:42:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
42 | #define loop(i,s,e) for (int (i)=(s);(i)<(e);++(i))
| ^
examination.cpp:47:18: note: in expansion of macro 'loop'
47 | #define rep(i,n) loop(i,0,n)
| ^~~~
examination.cpp:138:3: note: in expansion of macro 'rep'
138 | rep(i,n) if (s[i] >= 'a' && s[i] <= 'z') s[i] = s[i] - 'a' + 'A';
| ^~~
examination.cpp: In function 'std::string lowercase(std::string)':
examination.cpp:42:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
42 | #define loop(i,s,e) for (int (i)=(s);(i)<(e);++(i))
| ^
examination.cpp:47:18: note: in expansion of macro 'loop'
47 | #define rep(i,n) loop(i,0,n)
| ^~~~
examination.cpp:144:3: note: in expansion of macro 'rep'
144 | rep(i,n) if (s[i] >= 'A' && s[i] <= 'Z') s[i] = s[i] - 'A' + 'a';
| ^~~
examination.cpp: In function 'int get(int)':
examination.cpp:42:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
42 | #define loop(i,s,e) for (int (i)=(s);(i)<(e);++(i))
| ^
examination.cpp:195:5: note: in expansion of macro 'loop'
195 | loop(i,k,(curB+1)*B_SIZE) ans += f[i];
| ^~~~
examination.cpp:42:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
42 | #define loop(i,s,e) for (int (i)=(s);(i)<(e);++(i))
| ^
examination.cpp:196:5: note: in expansion of macro 'loop'
196 | loop(i,curB+1,block_ct) ans += block[i];
| ^~~~
examination.cpp: In function 'int main()':
examination.cpp:42:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
42 | #define loop(i,s,e) for (int (i)=(s);(i)<(e);++(i))
| ^
examination.cpp:47:18: note: in expansion of macro 'loop'
47 | #define rep(i,n) loop(i,0,n)
| ^~~~
examination.cpp:207:3: note: in expansion of macro 'rep'
207 | rep(i,n)
| ^~~
examination.cpp:42:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
42 | #define loop(i,s,e) for (int (i)=(s);(i)<(e);++(i))
| ^
examination.cpp:47:18: note: in expansion of macro 'loop'
47 | #define rep(i,n) loop(i,0,n)
| ^~~~
examination.cpp:247:3: note: in expansion of macro 'rep'
247 | rep(i,q)
| ^~~
examination.cpp:42:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
42 | #define loop(i,s,e) for (int (i)=(s);(i)<(e);++(i))
| ^
examination.cpp:47:18: note: in expansion of macro 'loop'
47 | #define rep(i,n) loop(i,0,n)
| ^~~~
examination.cpp:260:3: note: in expansion of macro 'rep'
260 | rep(i,q)
| ^~~
examination.cpp:9:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
9 | #define si2(x,y) scanf("%d %d",&x,&y)
| ~~~~~^~~~~~~~~~~~~~~
examination.cpp:69:30: note: in expansion of macro 'si2'
69 | #define takei2(a,b) int a,b; si2(a,b)
| ^~~
examination.cpp:204:3: note: in expansion of macro 'takei2'
204 | takei2(n,q);
| ^~~~~~
examination.cpp:9:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
9 | #define si2(x,y) scanf("%d %d",&x,&y)
| ~~~~~^~~~~~~~~~~~~~~
examination.cpp:69:30: note: in expansion of macro 'si2'
69 | #define takei2(a,b) int a,b; si2(a,b)
| ^~~
examination.cpp:209:5: note: in expansion of macro 'takei2'
209 | takei2(s,t);
| ^~~~~~
examination.cpp:9:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
9 | #define si2(x,y) scanf("%d %d",&x,&y)
| ~~~~~^~~~~~~~~~~~~~~
examination.cpp:69:30: note: in expansion of macro 'si2'
69 | #define takei2(a,b) int a,b; si2(a,b)
| ^~~
examination.cpp:249:5: note: in expansion of macro 'takei2'
249 | takei2(l,r); takei(k);
| ^~~~~~
examination.cpp:8:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
8 | #define si(x) scanf("%d",&x)
| ~~~~~^~~~~~~~~
examination.cpp:68:25: note: in expansion of macro 'si'
68 | #define takei(a) int a; si(a)
| ^~
examination.cpp:249:18: note: in expansion of macro 'takei'
249 | takei2(l,r); takei(k);
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
604 KB |
Output is correct |
| 2 |
Correct |
0 ms |
604 KB |
Output is correct |
| 3 |
Correct |
0 ms |
600 KB |
Output is correct |
| 4 |
Correct |
1 ms |
604 KB |
Output is correct |
| 5 |
Correct |
1 ms |
604 KB |
Output is correct |
| 6 |
Correct |
0 ms |
604 KB |
Output is correct |
| 7 |
Correct |
23 ms |
1880 KB |
Output is correct |
| 8 |
Correct |
25 ms |
1884 KB |
Output is correct |
| 9 |
Correct |
22 ms |
1884 KB |
Output is correct |
| 10 |
Correct |
7 ms |
1628 KB |
Output is correct |
| 11 |
Correct |
8 ms |
1628 KB |
Output is correct |
| 12 |
Correct |
7 ms |
1112 KB |
Output is correct |
| 13 |
Correct |
23 ms |
1884 KB |
Output is correct |
| 14 |
Correct |
22 ms |
2076 KB |
Output is correct |
| 15 |
Correct |
23 ms |
2076 KB |
Output is correct |
| 16 |
Correct |
10 ms |
1624 KB |
Output is correct |
| 17 |
Correct |
10 ms |
1372 KB |
Output is correct |
| 18 |
Correct |
7 ms |
1116 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3071 ms |
29960 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3071 ms |
29960 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
604 KB |
Output is correct |
| 2 |
Correct |
0 ms |
604 KB |
Output is correct |
| 3 |
Correct |
0 ms |
600 KB |
Output is correct |
| 4 |
Correct |
1 ms |
604 KB |
Output is correct |
| 5 |
Correct |
1 ms |
604 KB |
Output is correct |
| 6 |
Correct |
0 ms |
604 KB |
Output is correct |
| 7 |
Correct |
23 ms |
1880 KB |
Output is correct |
| 8 |
Correct |
25 ms |
1884 KB |
Output is correct |
| 9 |
Correct |
22 ms |
1884 KB |
Output is correct |
| 10 |
Correct |
7 ms |
1628 KB |
Output is correct |
| 11 |
Correct |
8 ms |
1628 KB |
Output is correct |
| 12 |
Correct |
7 ms |
1112 KB |
Output is correct |
| 13 |
Correct |
23 ms |
1884 KB |
Output is correct |
| 14 |
Correct |
22 ms |
2076 KB |
Output is correct |
| 15 |
Correct |
23 ms |
2076 KB |
Output is correct |
| 16 |
Correct |
10 ms |
1624 KB |
Output is correct |
| 17 |
Correct |
10 ms |
1372 KB |
Output is correct |
| 18 |
Correct |
7 ms |
1116 KB |
Output is correct |
| 19 |
Execution timed out |
3071 ms |
29960 KB |
Time limit exceeded |
| 20 |
Halted |
0 ms |
0 KB |
- |
