답안 #22393 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
22393	2017-04-30T04:22:28 Z	AcornCkiGs14004Team(#953, gs14004, cki86201, dotorya)	Donut-shaped Enclosure (KRIII5_DE)	C++14	0 / 7	6 ms	23412 KB

#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);
                                         ^

Subtask #1
0 / 2.0

#	결과	실행 시간	메모리	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	-

Subtask #2
0 / 5.0

#	결과	실행 시간	메모리	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	-

답안 #22393

Compilation message

Subtask #1 0 / 2.0

Subtask #2 0 / 5.0

Subtask #1
0 / 2.0

Subtask #2
0 / 5.0