Submission #224019

#	Time	Username	Problem	Language	Result	Execution time	Memory
224019		shenxy	Just Long Neckties (JOI20_ho_t1)	C++11	100 / 100	202 ms	27256 KiB

ho_t1

#include <cstdio>
#include <algorithm>
using namespace std;
typedef pair<long long, int> ii;
struct seg {
    int s, e, m, v;
    seg *l, *r;
    seg(int _s, int _e) {
        s = _s, e = _e, m = (s + e) / 2, v = 0;
        if (s != e) {
            l = new seg(s, m);
            r = new seg(m + 1, e);
        }
    }
    void update(int i, int nv) {
        if (s != e) {
            if (i > m) r -> update(i, nv);
            else l -> update(i, nv);
            v = max(l -> v, r -> v);
        } else v = nv;
    }
    int query(int a, int b) {
        if (s == a && e == b) return v;
        if (a > m) return r -> query(a, b);
        if (b <= m) return l -> query(a, b);
        return max(l -> query(a, m), r -> query(m + 1, b));
    }
} *root;
int main() {
	int N;
	scanf("%d", &N);
	ii A[N + 1];
	long long B[N], ans[N + 1];
	for (int i = 0; i <= N; ++i) scanf("%lld", &A[i].first), A[i].second = i;
	for (int i = 0; i < N; ++i) scanf("%lld", &B[i]);
	sort(A, A + N + 1);
	sort(B, B + N);
	root = new seg(0, N - 1);
	for (int i = 0; i < N; ++i) root -> update(i, max(A[i].first - B[i], 0LL));
	ans[A[N].second] = root -> query(0, N - 1);
	for (int i = N - 1; i >= 0; --i) {
		root -> update(i, max(A[i + 1].first - B[i], 0LL));
		ans[A[i].second] = root -> query(0, N - 1);
	}
	for (int i = 0; i <= N; ++i) printf("%lld ", ans[i]);
	return 0;
}

Compilation message (stderr)

ho_t1.cpp: In function 'int main()':
ho_t1.cpp:31:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
ho_t1.cpp:34:57: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 0; i <= N; ++i) scanf("%lld", &A[i].first), A[i].second = i;
                               ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
ho_t1.cpp:35:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 0; i < N; ++i) scanf("%lld", &B[i]);
                              ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 1 / 1
• Subtask 2: 8 / 8
• Subtask 3: 91 / 91