Submission #41253

#TimeUsernameProblemLanguageResultExecution timeMemory
41253grumpy_gordonSparklers (JOI17_sparklers)C++14
0 / 100
2 ms632 KiB
/* .:*+=%@@@@@@=-. .:=@#@@@#@@#######%==*. .-=####@######%*-.....:%##%. .*@###########%+:--........-%@- .*@##############@+--.........-:%- .+##################@==%%%%=+*:----+. .-@####################%++%@@@@@=+**%@@* .%###################@%%@@@###@%+:--%@@%. -@###################@%%%%*::*%++:-----=@+. -#####################@%=++++++*:-------.-=: .+####################@%++*::-:::--::*:::***=: .@#####################%=++*::::-:::++*=##@@#@- ..#####################@%%=++**:::::**+%@#@%%##-.. .%####################@@%=+++*+****::*=@######@. .=######################@%%==+==++**+=@%@##@###+:... -#######################@@@%%%===++=@@@%=++===*::--... -########################@@@@@@@%==%%=++==@@:::::*:--. ..:#########################@@@@@@%%======++++::-..:-.--... %#############################@###@%%@@%==%=%*----.--.::---. #############################################*-:*:-:---*---- . #############################################*--*--:---*---:-. #############################################+--::--::-*::-::. ###########################################+:*-.---.---.:---*-.. ###########################################**:-----------------. ##########################################@::**:--::::::--:::::- ###########################################:--:*:::::::::**::*+* ###########################################=:::***::::::**:::*+* ############################@@@@@@#########@+****::::********+++ ############################@%%%%%@@@@@@@###%+***::::::::***+==+ ############################@%%%%%%%%%%%@####=+:::-::::-::*+=%%+ #############################@%%%%%%%%%%@#####=::--------:*=%@%+ %###########################@%%%%==%%%%%%@##@#=:------..-:+%@@%= ---------------------------------------------- -------------------------------------------- ---------------------------------------------- -------------------------------------------- ---------------------------------------------- o###########oo o##" ""##o o#" "## o#" "#o #" ## ## "## #" ## # ################### # # # # # # # # # # # # # #o # "#o ## "#o ## "#o o#" "#o ## "#o o#" "#ooo ooo#######oo ############### "######o o###"" "###o # ### o###o oooo ### oo####" o###**# #**# ############" ""##""""""""""########### # # oooooooo#"#** ## # # # # # ** ## # #o# #o# *****###ooo# ## ## o###o ## o##***## o########## #***#**##o o##" ""### #***##***# o#######o ### oo#### ##**####*# o##" ""#############"" ##****### ##" ## ##*##*### ## ### ##### ## ## ### # ## # ## ## # ## ## ## ### ## ###oo ### ""### ### ### */ #include <bits/stdc++.h> //#pragma GCC optimize("O3") //#pragma GCC optimize("Ofast,no-stack-protector") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx") //#pragma GCC target("avx,tune=native") //float __attribute__((aligned(32))) using namespace std; typedef long long ll; typedef unsigned long long ull; typedef long double ld; int mysqrt(ll x){ int l = 0, r = 1e9 + 1; while (r - l > 1){ int m = (l + r) / 2; if (m * (ll)m <= x) l = m; else r = m; } return l; } mt19937 rnd(1337); ll AR = 19, BR = 13, CR = 23, XR = 228, YR = 322, MODR = 1e9 + 993; ll myrand(){ ll ZR = (XR * AR + YR * BR + CR) % MODR; XR = YR; YR = ZR; return ZR; } const int Mod = 1e9 + 7; int bpow(int x, int y){ if (y == 0) return 1; if (y == 1) return x; int ret = bpow(x, y >> 1); ret = (ret * (ll)ret) % Mod; if (y & 1) ret = (ret * (ll)x) % Mod; return ret; } int bdiv(int x, int y){ return (x * (ll)bpow(y, Mod - 2)) % Mod; } void setmin(int &x, int y){ x = min(x, y); } void setmax(int &x, int y){ x = max(x, y); } void setmin(ll &x, ll y){ x = min(x, y); } void setmax(ll &x, ll y){ x = max(x, y); } int gcd(int a, int b){ return a ? gcd(b % a, a) : b; } const ll llinf = 2e18 + 100; const double eps = 1e-9; const int maxn = 1e5 + 100, maxw = 1e6 + 100, inf = 2e9 + 100, sq = 300, mod = 1e9 + 7, LG = 17; int n, k, t; int a[maxn]; ll q[4 * maxn]; void build(int v, int l, int r, vector<ll> &arr){ if (l == r){ q[v] = arr[l]; return; } int m = (l + r) / 2; build(2 * v, l, m, arr); build(2 * v + 1, m + 1, r, arr); q[v] = max(q[2 * v], q[2 * v + 1]); } int get(int v, int tl, int tr, int l, int r, ll val){ if (l > r || q[v] < val) return -1; if (tl == tr) return tl; int m = (tl + tr) / 2; int ret = get(2 * v + 1, m + 1, tr, max(l, m + 1), r, val); if (ret != -1) return ret; return get(2 * v, tl, m, l, min(r, m), val); } bool check(int S){ vector<ll> A, B; A.push_back(0); for (int i = k - 1; i >= 0; i--) A.push_back(-a[i] + min((ll)inf, 2 * S * (ll)t)); B.push_back(0); for (int i = k; i < n; i++) B.push_back(B.back() + -a[i] + min((ll)inf, 2 * S * (ll)t)); build(1, 0, B.size() - 1, B); vector<ll> C(B.size()); C[0] = 0; for (int i = 1; i < C.size(); i++) C[i] = min(C[i - 1], B[i]); int last = 0; int l, r; l = -1, r = C.size(); while (r - l > 1){ int m = (l + r) / 2; if (C[m] >= 0) l = m; else r = m; } last = l; ll sum = 0; for (int i = 1; i < A.size(); i++){ int val = A[i]; sum += val; if (val >= 0){ l = last, r = C.size(); while (r - l > 1){ int m = (l + r) / 2; if (C[m] + sum >= 0) l = m; else r = m; } last = l; } else{ last = get(1, 0, B.size() - 1, 0, last, -sum); if (last == -1) return 0; } } return last == B.size() - 1; } int main() { #ifdef ONPC //ifstream cin("a.in"); //ofstream cout("a.out"); freopen("a.in", "r", stdin); freopen("a.out", "w", stdout); #else //ifstream cin("sprinklers.in"); //ofstream cout("sprinklers.out"); //freopen("road.in", "r", stdin); //freopen("road.out", "w", stdout); #endif // ONPC ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> k >> t; k--; for (int i = 0; i < n; i++){ cin >> a[i]; if (i) a[i - 1] = a[i] - a[i - 1]; } n--; int l = -1, r = (1e9 + (ll)2 * t - 1) / (2 * t); while (r - l > 1){ int m = (l + r) / 2; if (check(m)) r = m; else l = m; } cout << r; }

Compilation message (stderr)

sparklers.cpp: In function 'bool check(int)':
sparklers.cpp:209:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 1; i < C.size(); i++)
                       ^
sparklers.cpp:223:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 1; i < A.size(); i++){
                       ^
sparklers.cpp:243:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     return last == B.size() - 1;
                 ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...