Submission #22928

#	Time	Username	Problem	Language	Result	Execution time	Memory
22928		dotorya	Donut-shaped Enclosure (KRIII5_DE)	C++14	7 / 7	613 ms	25036 KiB

DE

#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:
	int mx, v;
	Node() { mx = 0, v = 0; }
};
Node indt[1100000];
void update(int st, int en, int S, int E, int n, int v) {
	if (st > en) return;
	if (st == S && en == E) {
		indt[n].mx += v;
		indt[n].v += v;
		return;
	}

	int M = (S + E) / 2;
	update(st, min(en, M), S, M, 2 * n, v);
	update(max(M + 1, st), en, M + 1, E, 2 * n + 1, v);
	indt[n].mx = indt[n].v + max(indt[2 * n].mx, indt[2 * n + 1].mx);
}

vector <pair<pii, pii>> Vq;
vector <int> Vy;
int main() {
	int N, L, R, i;
	scanf("%d %d %d", &N, &L, &R);
	while (N--) {
		int t1, t2, t3;
		scanf("%d %d %d", &t1, &t2, &t3);

		Vq.emplace_back(pii(t1 - R, t3), pii(t2 - R, t2 + R + 1));
		Vq.emplace_back(pii(t1 + R + 1, -t3), pii(t2 - R, t2 + R + 1));
		Vq.emplace_back(pii(t1 - L + 1, -t3), pii(t2 - L + 1, t2 + L));
		Vq.emplace_back(pii(t1 + L, t3), pii(t2 - L + 1, t2 + L));

		Vy.push_back(t2 - R);
		Vy.push_back(t2 + R + 1);
		Vy.push_back(t2 - L + 1);
		Vy.push_back(t2 + L);
	}
	sort(all(Vy));
	Vy.erase(unique(all(Vy)), Vy.end());

	for (auto &it : Vq) {
		it.second.first = lower_bound(all(Vy), it.second.first) - Vy.begin() + 1;
		it.second.second = lower_bound(all(Vy), it.second.second) - Vy.begin();
	}
	sort(all(Vq));

	int ans = 0;
	for (i = 0; i < Vq.size(); i++) {
		int t1 = Vq[i].first.first, t2 = Vq[i].first.second, t3 = Vq[i].second.first, t4 = Vq[i].second.second;
		update(t3, t4, 1, IT_MAX, 1, t2);
		if (i + 1 == Vq.size() || Vq[i].first.first != Vq[i + 1].first.first) ans = max(ans, indt[1].mx);
	}
	return !printf("%d\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:101:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (i = 0; i < Vq.size(); i++) {
                ^
DE.cpp:104: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:102:7: warning: unused variable 't1' [-Wunused-variable]
   int t1 = Vq[i].first.first, t2 = Vq[i].first.second, t3 = Vq[i].second.first, t4 = Vq[i].second.second;
       ^
DE.cpp:76:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d", &N, &L, &R);
                               ^
DE.cpp:79:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &t1, &t2, &t3);
                                   ^

• Subtask 1: 2 / 2
• Subtask 2: 5 / 5