답안 #437925

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
437925 2021-06-27T09:38:41 Z hhhhaura 사탕 분배 (IOI21_candies) C++17
0 / 100
308 ms 22960 KB
#define wiwihorz
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma loop-opt(on)

#define rep(i, a, b) for(int i = a; i <= b; i ++)
#define rrep(i, a, b) for(int i = b; i >= a; i--)
#define ceil(a, b) ((a + b - 1) / (b))
#define all(x) x.begin(), x.end()

#define INF 1000000000000000000
#define MOD 1000000007
#define eps (1e-9)

using namespace std;

#define ll long long int
#define lld long double
#define pii pair<ll, ll>
#define random mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count())

#ifdef wiwihorz
#define print(a...) cerr << "line " << __LINE__ << ": ", kout("[" + string(#a) + "] = ", a)
void vprint(auto L, auto R) { while(L < R) cerr << *L << " \n"[next(L) == R], ++L;}
void kout() { cerr << endl; }
template<class T1, class ... T2> void kout(T1 a, T2 ... e) { cerr << a << " ", kout(e...);}
#else
#define print(...) 0
#define vprint(...) 0
#endif 

#include "candies.h"
namespace seg {
	int n;
	vector<ll> tag;
	vector<pii> mx, mn;
	int get(int L, int R) { return (L + R) | (L != R);}
	void pull(int L, int R) {
		int nd = get(L, R), mid = (L + R) / 2;
		int l = get(L, mid), r = get(mid + 1, R);
		mx[nd] = max(
			pii(mx[l].first + tag[l], mx[l].second),
			pii(mx[r].first + tag[r], mx[r].second)
		);
		mn[nd] = min(
			pii(mn[l].first + tag[l], mn[l].second),
			pii(mn[r].first + tag[r], mn[r].second)
		);
	}
	void push(int L, int R) {
		int nd = get(L, R), mid = (L + R) / 2;
		int l = get(L, mid), r = get(mid + 1, R);
		tag[l] += tag[nd];
		tag[r] += tag[nd];
		mn[nd].first += tag[nd];
		mx[nd].first += tag[nd];
		tag[nd] = 0;
	}
	void build(int L, int R) {
		int nd = get(L, R), mid = (L + R) / 2;
		if(L == R) mx[nd] = {0, L}, mn[nd] = {0, -L};
		else {
			build(L, mid);
			build(mid + 1, R);
			pull(L, R);
		}
	} 
	void init_(int _n) {
		n = _n;
		tag.assign(2 * n + 1, 0);
		mx.assign(2 * n + 1, {0, 0});
		mn.assign(2 * n + 1, {0, 0});
		build(1, n);
	}
	void modify(int L, int R, int l, int r, int val) {
		int mid = (L + R) / 2, nd = get(L, R);
		if(l > R || r < L) return;
		if(L != R) push(L, R);
		if(l <= L && r >= R) tag[nd] += val;
		else {
			modify(L, mid, l, r, val);
			modify(mid + 1, R, l, r, val);
			pull(L, R);
		}
	}
	pii get_pii(int nd, int id) {
		if(id == 0) return {mn[nd].first + tag[nd], mn[nd].second};
		else return {mx[nd].first + tag[nd], mx[nd].second};
	}
	ll bs(int L, int R, int c, pii big, pii sm) {
		int mid = (L + R) / 2, nd = get(L, R);
		int l = get(L, mid), r = get(mid + 1, R);
		if(L == R) {
			big = max(big, get_pii(nd, 1));
			sm = min(sm, get_pii(nd, 0));
			assert(big.first - sm.first >= c);
			if(big.second >= -sm.second) return big.first;
			else return sm.first;
		}
		else {
			push(L, R);
			ll rmx = max(big.first, tag[r] + mx[r].first);
			ll rmn = min(sm.first, tag[r] + mn[r].first);
			if(rmx - rmn >= c) return bs(mid + 1, R, c, big, sm);
			else return bs(L, mid, c, max(big, get_pii(r, 1)), min(sm, get_pii(r, 0)));
		}
	}
	void change(int x, ll val) { modify(1, n, x, n, val);}
	ll query(ll c) { return bs(1, n, c, {-INF, -INF}, {INF, INF});}
};
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
    int n = c.size(), m = l.size(), sum = 0;
 	vector<int> ans(n, 0);
 	// 全部都往後墊3
 	seg::init_(m + 2);
 	seg::change(1, -INF);
 	seg::change(2, INF);
 	rep(i, 3, m + 2) seg::change(i, v[i - 3]), sum += v[i - 3];
 	rep(i, 0, n - 1) ans[i] = (sum - seg::query(c[i]) + c[i]) % c[i]; 
    return ans;
}

Compilation message

candies.cpp:4: warning: ignoring '#pragma loop ' [-Wunknown-pragmas]
    4 | #pragma loop-opt(on)
      | 
candies.cpp:24:13: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   24 | void vprint(auto L, auto R) { while(L < R) cerr << *L << " \n"[next(L) == R], ++L;}
      |             ^~~~
candies.cpp:24:21: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   24 | void vprint(auto L, auto R) { while(L < R) cerr << *L << " \n"[next(L) == R], ++L;}
      |                     ^~~~
candies.cpp: In function 'long long int seg::bs(int, int, int, std::pair<long long int, long long int>, std::pair<long long int, long long int>)':
candies.cpp:92:7: warning: unused variable 'l' [-Wunused-variable]
   92 |   int l = get(L, mid), r = get(mid + 1, R);
      |       ^
# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 308 ms 22960 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -