답안 #435141

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
435141 2021-06-23T03:58:49 Z Kevin_Zhang_TW 사탕 분배 (IOI21_candies) C++17
컴파일 오류
0 ms 0 KB
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
#include "candies.h"

const int MAX_N = 200010;
const ll inf = 1ll << 59;

int n, m;
struct node {
	ll mx, mn, at;
	void operator += (ll v) { mx += v, mn += v, at += v; }
	node (ll a, ll b) : mx(a), mn(b), at(0) {}
	node (ll v) : at(0), mx(v), mn(v) {}
	node (node a, node b) : at(0), mx(max(a.mx, b.mx)), mn(min(a.mn, b.mn)) {}
	node () : mx(0), mn(0), at(0) {}
	bool valid(int c) { return mx - mn <= c; }
};

vector<pair<ll,ll>> op[MAX_N];

sturct sgt {
	int n;
	vector<node> val;
	sgt(int n) : n(n) {
		val.resize(n<<1);
	}
	void push(int i) {
		if (i >= n) return;
		val[i<<1] += val[i].at;
		val[i<<1|1] += val[i].at;
		val[i].at = 0;
	}
	void upd(int i) {
		if (i >= n) return;
		push(i);
		val[i] = node(val[i<<1], val[i<<1|1]);
	}
	void add(int l, int r, ll v) {
		l += n, r += n;
		int sl = l, sr = r;
		for (;l < r;l>>=1, r>>=1) {
			if (l&1) val[l++] += v;
			if (r&1) val[--r] += v;
		}
		for (;sl>>=1, sr>>=1;)
			upd(sl), upd(sr);
	}
	node qry(int l, int r) {
		l += n, r += n;
		for (int i = 18;i > 0;--i) push(l>>i), push(r>>i);
		node ret(-inf, inf);
		for (;l < r;l>>=1, r>>=1) {
			if (l&1) ret = node(ret, val[l++]);
			if (r&1) ret = node(ret, val[--r]);
		}
		return ret;
	}
}tree(0);

int qry(int c) {
	auto s0 = tree.qry(0, m);
	ll all = tree.qry(m-1, m), mx;
	if (s0.mx - s0.mn <= c) {
		return all - s0.mn;
	}
	int l = 0, r = m-1, mid;
	while (l < r) {
		mid = l + r >> 1;
		if (tree.qry(mid, m).valid(c))
			r = mid;
		else
			l = mid+1;
	}
	assert(l > 0);
	ll v = tree.qry(l-1, k).mx;
	auto sl = tree.qry(l, m);
	if (sl.mx > v + c) {
		return c + (all - sl.mx);
	}
	else return all - sl.mn;
}
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
	n = c.size(), m = l.size();
	for (int i = 0;i < m;++i) {
		op[l[i]].pb(i+1, v[i]);
		op[r[i]+1].pb(i+1, -v[i]);
	}
	++m;
	tree = sgt(m);
	vector<int> res(n);
	for (int i = 0;i < n;++i) {
		for (auto [j, w] : op[i]) 
			tree.add(j, m, w);
		res[i] = qry(c[i]);
	}
	return res;
}

Compilation message

candies.cpp: In constructor 'node::node(ll)':
candies.cpp:24:13: warning: 'node::at' will be initialized after [-Wreorder]
   24 |  ll mx, mn, at;
      |             ^~
candies.cpp:24:5: warning:   'll node::mx' [-Wreorder]
   24 |  ll mx, mn, at;
      |     ^~
candies.cpp:27:2: warning:   when initialized here [-Wreorder]
   27 |  node (ll v) : at(0), mx(v), mn(v) {}
      |  ^~~~
candies.cpp: In constructor 'node::node(node, node)':
candies.cpp:24:13: warning: 'node::at' will be initialized after [-Wreorder]
   24 |  ll mx, mn, at;
      |             ^~
candies.cpp:24:5: warning:   'll node::mx' [-Wreorder]
   24 |  ll mx, mn, at;
      |     ^~
candies.cpp:28:2: warning:   when initialized here [-Wreorder]
   28 |  node (node a, node b) : at(0), mx(max(a.mx, b.mx)), mn(min(a.mn, b.mn)) {}
      |  ^~~~
candies.cpp: At global scope:
candies.cpp:35:1: error: 'sturct' does not name a type; did you mean 'struct'?
   35 | sturct sgt {
      | ^~~~~~
      | struct
candies.cpp:72:6: error: expected constructor, destructor, or type conversion before '(' token
   72 | }tree(0);
      |      ^
candies.cpp: In function 'int qry(int)':
candies.cpp:75:12: error: 'tree' was not declared in this scope; did you mean 'free'?
   75 |  auto s0 = tree.qry(0, m);
      |            ^~~~
      |            free
candies.cpp:82:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   82 |   mid = l + r >> 1;
      |         ~~^~~
candies.cpp:89:23: error: 'k' was not declared in this scope
   89 |  ll v = tree.qry(l-1, k).mx;
      |                       ^
candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:103:2: error: 'tree' was not declared in this scope; did you mean 'free'?
  103 |  tree = sgt(m);
      |  ^~~~
      |  free
candies.cpp:103:9: error: 'sgt' was not declared in this scope; did you mean 'sig_t'?
  103 |  tree = sgt(m);
      |         ^~~
      |         sig_t