This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma GCC optimize("Ofast")
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cstring>
#include <iomanip>
#include <vector>
#include <bitset>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#define endl '\n'
#define X first
#define Y second
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
const int maxn = 2e5+10;
const int bl = 320;
const int sq = 400;
//const int bl = 2;
//const int sq = 10000;
pii arr[maxn];
struct qr
{
int x, y, z, i;
} qrs[maxn];
int perm[maxn];
vector<int> qsts[maxn];
int ans[maxn];
inline bool cmpsum(pii a, pii b)
{
return a.X+a.Y > b.X+b.Y;
}
inline bool cmpq(int i, int j)
{
return qrs[i].x > qrs[j].x;
}
pii trr[maxn];
int tbr[maxn];
inline int get_gcnt(int s, int b)
{
return upper_bound(tbr, tbr+s, b, greater<int>()) - tbr;
}
int32_t main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n, q; cin >> n >> q;
for(int i = 0; i < n; i++)
{
cin >> arr[i].X >> arr[i].Y;
}
sort(arr, arr+n, cmpsum);
//cerr << n << endl;
//for(int i = 0; i < n; i++)
// cerr << arr[i].X << " " << arr[i].Y << endl;
//cerr << "---" << endl;
for(int i = 0; i < q; i++)
{
cin >> qrs[i].x >> qrs[i].y >> qrs[i].z;
qrs[i].i = i;
}
iota(perm, perm+q, 0);
sort(perm, perm+q, cmpq);
for(int idx = 0; idx < q; idx++)
{
int i = perm[idx];
for(int j = 0; j*bl < n; j++)
{
int e = min(n, j*bl+bl);
if( (arr[e-1].X + arr[e-1].Y) >= qrs[i].z)
{
qsts[j].push_back(i);
}
else
{
for(int k = j*bl; k < e; k++)
{
if(arr[k].X >= qrs[i].x and arr[k].Y >= qrs[i].y and (arr[k].X+arr[k].Y) >= qrs[i].z)
ans[i]++;
}
break;
}
}
}
for(int i = 0; i*bl < n; i++)
{
int s = i*bl;
int e = min(n, i*bl+bl);
int sz = e-s;
for(int j = s; j < e; j++)
trr[j-s] = arr[j];
sort(trr, trr+sz, greater<pii>());
//sort(qsts[i].begin(), qsts[i].end(), cmpq);
int p = 0;
int qs = qsts[i].size();
for(int j = 0; j < sz; j++)
{
while(p < qs and qrs[qsts[i][p]].x > trr[j].X)
{
ans[qsts[i][p]] += get_gcnt(j, qrs[qsts[i][p]].y);
p++;
}
{
tbr[j] = trr[j].Y;
int x = j;
while(x > 0 and tbr[x] > tbr[x-1])
{
swap(tbr[x], tbr[x-1]);
x--;
}
}
}
while(p < qs)
{
ans[qsts[i][p]] += get_gcnt(sz, qrs[qsts[i][p]].y);
p++;
}
}
for(int i = 0; i < q; i++)
cout << ans[i] << endl;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |