oj.uz

답안 #437998

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
437998 2021-06-27T11:54:28 Z hhhhaura 사탕 분배 (IOI21_candies) C++17
0 / 100
 308 ms 23236 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 1e9
#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);}
	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};
	}
	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(get_pii(l, 1), get_pii(r, 1));
		mn[nd] = min(get_pii(l, 0), get_pii(r, 0));
	}
	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);
		}
	}
	int qqq(int L, int R, int x) {
		if(L == R) return tag[get(L, R)] + mx[get(L, R)].first;
		else {
			push(L, R);
			int mid = (L + R) / 2;
			if(x <= mid) return qqq(L, mid, x);
			else return qqq(mid + 1, R, x);
		}
	}
	pii 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));
			if(big.second >= -sm.second) return {big.first, 1};
			else return {sm.first, 0};
		}
		else {
			push(L, R);
			ll rmx = max(big, get_pii(r, 1)).first;
			ll rmn = min(sm, get_pii(r, 0)).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);}
	pii query(ll c) { return bs(1, n, c, {-2 * INF, -2 * INF}, {2 * INF, 2 * INF});}
};
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
    int n = c.size(), m = l.size();
    ll sum = 0;
 	vector<int> ans(n, 0);
 	// 全部都往後墊3
 	seg::init_(m + 3);
 	seg::change(1, -INF);
 	seg::change(2, 2 * INF);
 	seg::change(3, -INF);
 	rep(i, 4, m + 3) seg::change(i, v[i - 4]), sum += (ll)v[i - 4];
 	rep(i, 0, n - 1) {
 		pii cur = seg::query(c[i]);
 		if(cur.second) ans[i] = c[i] + sum - cur.first;
 		else ans[i] = sum - cur.first;
 	} 
    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 'std::pair<long long int, 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:95:7: warning: unused variable 'l' [-Wunused-variable]
   95 |   int l = get(L, mid), r = get(mid + 1, R);
      |       ^

Subtask #1
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 1 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 304 ms 23108 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 185 ms 20564 KB Output is correct
4 Correct 94 ms 2868 KB Output is correct
5 Correct 305 ms 22968 KB Output is correct
6 Correct 308 ms 23236 KB Output is correct
7 Incorrect 286 ms 23012 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 1 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -