Submission #22393

#TimeUsernameProblemLanguageResultExecution timeMemory
22393AcornCkiGs14004Team (#40)Donut-shaped Enclosure (KRIII5_DE)C++14
0 / 7
6 ms23412 KiB
#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 (stderr)

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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...