#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <map>
#include <cstring>
#include <string>
#include <cmath>
#include <cassert>
#include <ctime>
#include <algorithm>
#include <sstream>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <cstdlib>
#include <cstdio>
#include <iterator>
#include <functional>
#include <unordered_set>
#include <unordered_map>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define pii pair<int, int>
#define vi vector<int>
#define fast_io ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
typedef long long ll;
typedef short inth;
const int N = 8e5;
const int M = N + 7;
const int K = 2e5;
const int MOD = 1e9 + 7;
const ll INF = 1e16 + 17;
map<int, int> px, py;
struct Point {
int x, y;
int power;
int id;
int comx, comy;
Point(int x, int y, int id, int new_power = -1) :
x(x), y(y), power(new_power), id(id), comx(0), comy(0) {
if (new_power == -1)
power = x + y;
};
void compress() {
comx = px[x];
comy = py[y];
}
};
vector<Point> p, w[2];
int n, m;
inline void read() {
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; ++i) {
int cx, cy;
scanf("%d %d", &cx, &cy);
p.pb(Point(cx, cy, i));
}
for (int i = 1; i <= m; ++i) {
int cx, cy, cs;
scanf("%d %d %d", &cx, &cy, &cs);
if (cx + cy >= cs)
w[0].pb(Point(cx, cy, i, cs));
else
w[1].pb(Point(cx, cy, i, cs));
}
}
inline void compress() {
vector<int> ordx, ordy;
for (int i = 0; i < n; ++i) {
ordx.pb(p[i].x);
ordy.pb(p[i].y);
}
for (int j = 0; j < 2; ++j)
for (int i = 0; i < sz(w[j]); ++i) {
ordx.pb(w[j][i].x);
ordy.pb(w[j][i].y);
}
sort(all(ordx));
sort(all(ordy));
int timx = 0, timy = 0;
for (int i = 0; i < sz(ordx); ++i) {
if (!i || ordx[i] != ordx[i - 1])
px[ordx[i]] = ++timx;
if (!i || ordy[i] != ordy[i - 1])
py[ordy[i]] = ++timy;
}
for (int i = 0; i < n; ++i)
p[i].compress();
for (int i = 0; i < sz(w[0]); ++i)
w[0][i].compress();
for (int i = 0; i < sz(w[1]); ++i)
w[1][i].compress();
}
struct Tree {
int g[M];
void build() {
for (int i = 0; i < M; ++i)
g[i] = 0;
}
void upd(int pos, int val, int v = 1, int tl = 1, int tr = K) {
if (tl == tr) {
g[v] += val;
return;
}
int tm = (tl + tr) >> 1;
if (pos <= tm)
upd(pos, val, v << 1, tl, tm);
else
upd(pos, val, v << 1 | 1, tm + 1, tr);
g[v] = g[v << 1] + g[v << 1 | 1];
}
int get(int l, int r, int v = 1, int tl = 1, int tr = K) {
if (tr < l || r < tl)
return 0;
if (l <= tl && tr <= r)
return g[v];
int tm = (tl + tr) >> 1;
int f = get(l, r, v << 1, tl, tm);
int s = get(l, r, v << 1 | 1, tm + 1, tr);
return f + s;
}
} tree[2];
inline bool cmpX(const Point& a, const Point& b) {
return a.x > b.x;
}
int ans[M];
inline void solve1() {
sort(w[0].begin(), w[0].end(), cmpX);
sort(all(p), cmpX);
int j = 0;
tree[0].build();
for (int i = 0; i < sz(w[0]); ++i) {
while (j < sz(p) && p[j].x >= w[0][i].x) {
tree[0].upd(p[j].y, 1);
++j;
}
int res = tree[0].get(w[0][i].y, K);
ans[w[0][i].id] = res;
}
}
inline bool cmpPower(const Point& a, const Point& b) {
return a.power > b.power;
}
inline void solve2() {
sort(w[1].begin(), w[1].end(), cmpPower);
sort(all(p), cmpPower);
int j = 0;
tree[0].build();
tree[1].build();
for (int i = 0; i < sz(w[1]); ++i) {
while (j < sz(p) && p[j].power >= w[1][i].power) {
tree[0].upd(p[j].x, 1);
tree[1].upd(p[j].y, 1);
++j;
}
int res = tree[0].get(1, w[1][i].x - 1) + tree[1].get(1, w[1][i].y - 1);
ans[w[1][i].id] = j - res;
}
}
inline void out() {
for (int i = 1; i <= m; ++i)
printf("%d\n", ans[i]);
}
int main() {
read();
//compress();
solve1();
solve2();
out();
return 0;
}
Compilation message
examination.cpp: In function 'void read()':
examination.cpp:70:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &n, &m);
~~~~~^~~~~~~~~~~~~~~~~
examination.cpp:74:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &cx, &cy);
~~~~~^~~~~~~~~~~~~~~~~~~
examination.cpp:81:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &cx, &cy, &cs);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
6520 KB |
Output is correct |
| 2 |
Correct |
8 ms |
6520 KB |
Output is correct |
| 3 |
Correct |
8 ms |
6648 KB |
Output is correct |
| 4 |
Incorrect |
8 ms |
6520 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
155 ms |
12384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
155 ms |
12384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
6520 KB |
Output is correct |
| 2 |
Correct |
8 ms |
6520 KB |
Output is correct |
| 3 |
Correct |
8 ms |
6648 KB |
Output is correct |
| 4 |
Incorrect |
8 ms |
6520 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
