#include <stdio.h>
#include <algorithm>
#include <assert.h>
#include <cmath>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits.h>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <time.h>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#pragma warning(disable:4996)
#pragma comment(linker, "/STACK:336777216")
using namespace std;
#define mp make_pair
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define szz(x) ((int)(x).size())
#define rep(i, n) for(int i=0;i<n;i++)
#define all(x) (x).begin(), (x).end()
#define ldb ldouble
typedef tuple<int, int, int> t3;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <ll, int> pli;
typedef pair <db, db> pdd;
int IT_MAX = 1 << 19;
const ll MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 1034567890123456789ll;
const db PI = acos(-1);
const db ERR = 1E-11;
class Node {
public:
ll mx;
ll v;
Node() {
mx = 0, v = 0;
}
};
Node indt[1200000];
void update(int st, int en, int S, int E, int n, ll v) {
if (st == S && en == E) {
indt[n].mx += v;
indt[n].v += v;
return;
}
int M = (S + E) / 2;
if (indt[n].v) {
indt[2 * n].mx += indt[n].v;
indt[2 * n].v += indt[n].v;
indt[2 * n + 1].mx += indt[n].v;
indt[2 * n + 1].v += indt[n].v;
indt[n].v = 0;
}
if (en <= M) update(st, en, S, M, 2 * n, v);
else if (st > M) update(st, en, M + 1, E, 2 * n + 1, v);
else {
update(st, M, S, M, 2 * n, v);
update(M + 1, en, M + 1, E, 2 * n + 1, v);
}
indt[n].mx = max(indt[2 * n].mx, indt[2 * n + 1].mx);
}
vector <pair<pll, pll>> Vq;
vector <ll> Vx;
vector <ll> Vy;
ll Qu[100050][3];
int main() {
int N, i;
ll L, R;
ll t1, t2, t3;
scanf("%d %lld %lld", &N, &L, &R);
for(i = 1; i <= N; i++) {
scanf("%lld %lld %lld", &t1, &t2, &t3);
Qu[i][0] = t1, Qu[i][1] = t2, Qu[i][2] = t3;
Vx.push_back(t1 - L + 1);
Vx.push_back(t1 + L - 1);
Vx.push_back(t1 - R);
Vx.push_back(t1 + R);
Vy.push_back(t2 - L + 1);
Vy.push_back(t2 + L - 1);
Vy.push_back(t2 - R);
Vy.push_back(t2 + R);
}
sort(all(Vx));
sort(all(Vy));
Vx.erase(unique(all(Vx)), Vx.end());
Vy.erase(unique(all(Vy)), Vy.end());
for (i = 1; i <= N; i++) {
ll t1 = Qu[i][0], t2 = Qu[i][1], t3 = Qu[i][2];
int sx = lower_bound(all(Vx), t1 - R) - Vx.begin() + 1;
int ex = lower_bound(all(Vx), t1 + R) - Vx.begin() + 1;
int sy = lower_bound(all(Vy), t2 - R) - Vy.begin() + 1;
int ey = lower_bound(all(Vy), t2 + R) - Vy.begin() + 1;
Vq.emplace_back(pll(sx, t3), pll(sy, ey));
Vq.emplace_back(pll(ex + 1, -t3), pll(sy, ey));
sx = lower_bound(all(Vx), t1 - L + 1) - Vx.begin() + 1;
ex = lower_bound(all(Vx), t1 + L - 1) - Vx.begin() + 1;
sy = lower_bound(all(Vy), t2 - L + 1) - Vy.begin() + 1;
ey = lower_bound(all(Vy), t2 + L - 1) - Vy.begin() + 1;
Vq.emplace_back(pll(sx, -t3), pll(sy, ey));
Vq.emplace_back(pll(ex + 1, t3), pll(sy, ey));
}
sort(all(Vq));
ll ans = 0;
for (i = 0; i < Vq.size(); i++) {
int sy = Vq[i].second.first;
int ey = Vq[i].second.second;
ll v = Vq[i].first.second;
update(sy, ey, 1, IT_MAX, 1, v);
if (i + 1 == Vq.size() || Vq[i].first.first != Vq[i + 1].first.first) ans = max(ans, indt[1].mx);
}
return !printf("%lld\n", ans);
}
Compilation message
DE.cpp:22:0: warning: ignoring #pragma warning [-Wunknown-pragmas]
#pragma warning(disable:4996)
^
DE.cpp:23:0: warning: ignoring #pragma comment [-Wunknown-pragmas]
#pragma comment(linker, "/STACK:336777216")
^
DE.cpp: In function 'int main()':
DE.cpp:138:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i = 0; i < Vq.size(); i++) {
^
DE.cpp:144:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (i + 1 == Vq.size() || Vq[i].first.first != Vq[i + 1].first.first) ans = max(ans, indt[1].mx);
^
DE.cpp:98:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %lld %lld", &N, &L, &R);
^
DE.cpp:100:41: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld %lld %lld", &t1, &t2, &t3);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
23120 KB |
Output is correct |
| 2 |
Correct |
0 ms |
23120 KB |
Output is correct |
| 3 |
Correct |
6 ms |
23120 KB |
Output is correct |
| 4 |
Correct |
3 ms |
23120 KB |
Output is correct |
| 5 |
Correct |
3 ms |
23120 KB |
Output is correct |
| 6 |
Correct |
6 ms |
23276 KB |
Output is correct |
| 7 |
Correct |
6 ms |
23264 KB |
Output is correct |
| 8 |
Correct |
3 ms |
23264 KB |
Output is correct |
| 9 |
Correct |
6 ms |
23412 KB |
Output is correct |
| 10 |
Incorrect |
6 ms |
23412 KB |
Output isn't correct |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
23120 KB |
Output is correct |
| 2 |
Correct |
0 ms |
23120 KB |
Output is correct |
| 3 |
Correct |
6 ms |
23120 KB |
Output is correct |
| 4 |
Correct |
3 ms |
23120 KB |
Output is correct |
| 5 |
Correct |
3 ms |
23120 KB |
Output is correct |
| 6 |
Correct |
6 ms |
23276 KB |
Output is correct |
| 7 |
Correct |
6 ms |
23264 KB |
Output is correct |
| 8 |
Correct |
3 ms |
23264 KB |
Output is correct |
| 9 |
Correct |
6 ms |
23412 KB |
Output is correct |
| 10 |
Incorrect |
6 ms |
23412 KB |
Output isn't correct |
| 11 |
Halted |
0 ms |
0 KB |
- |
