Submission #375197

#TimeUsernameProblemLanguageResultExecution timeMemory
375197LightningPo (COCI21_po)C++14
20 / 70
57 ms2304 KiB
#pragma GCC optimize("Ofast") #pragma GCC target("sse,sse2,sse3,sse3,sse4,popcnt,abm,mmx") #include <iostream> #include <algorithm> #include <vector> #include <cmath> #include <set> #include <map> #include <iomanip> #include <cassert> #include <stack> #include <queue> #include <deque> //#include <ext/pb_ds/assoc_container.hpp> //#include <ext/pb_ds/tree_policy.hpp>- using namespace std; //using namespace __gnu_pbds; typedef long long ll; typedef pair <int, int> pii; typedef pair <ll, ll> pll; // template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; // order_of_key (k) : Number of items strictly smaller than k . // find_by_order(k) : K-th element in a set (counting from zero). #define sz(a) (int)a.size() #define all(a) a.begin(), a.end() #define pb push_back #define ppb pop_back #define mkp make_pair #define F first #define S second #define lb lower_bound #define ub upper_bound #define show(a) cerr << #a <<" -> "<< a <<" " #define nl cerr <<"\n" //#define int ll const int N = (1 << 17) - 1; const int oo = 1e9 + 5; int n, t[N*3], add[N*3]; void push(int v, int tl, int tr) { if (add[v] != 0) { t[v] += add[v]; if (tl < tr) { add[v*2] += add[v]; add[v*2+1] += add[v]; } add[v] = 0; } } void upd(int l, int r, int x, int v=1, int tl=1, int tr=n) { push(v, tl, tr); if (r < tl || tr < l) { return; } if (l <= tl && tr <= r) { add[v] += x; push(v, tl, tr); return; } int tm = (tl + tr) / 2; upd(l, r, x, v*2, tl, tm); upd(l, r, x, v*2+1, tm+1, tr); t[v] = max(t[v*2], t[v*2+1]); } // самый левый у которого значение 0 < val pii get(int v=1, int tl=1, int tr=n) { push(v, tl, tr); if (tl == tr) { return {tl, t[v]}; } int tm = (tl + tr) / 2; if (0 < t[v*2] + add[v*2]) { return get(v*2, tl, tm); } return get(v*2+1, tm+1, tr); } pii get1(int v=1, int tl=1, int tr=n) { push(v, tl, tr); if (tl == tr) { return {tl, t[v]}; } int tm = (tl + tr) / 2; if (t[v*2] + add[v*2] < 0) { return get1(v*2, tl, tm); } return get1(v*2+1, tm+1, tr); } /*int get1(int pos, int v=1, int tl=1, int tr=n) { push(v, tl, tr); if (tl == tr) { return t[v]; } int tm = (tl + tr) / 2; if (pos <= tm) { return get1(pos, v*2, tl, tm); } return get1(pos, v*2+1, tm+1, tr); }*/ void solve() { cin >> n; for (int i = 1; i <= n; ++i) { int x; cin >> x; upd(i, i, x); } int ans = 0; for (int i = 1; i <= n; ++i) { pii p = get(); if (p.S == 0) { break; } upd(p.F, n, -p.S); pii q = get1(); if (q.S < 0) { upd(q.F, n, +p.S); } ++ans; } cout << ans; } main () { ios_base::sync_with_stdio(false); cin.tie(NULL); int tests = 1; //cin >> tests; while (tests --) { solve(); } return 0; } /* Just Chalish! */

Compilation message (stderr)

Main.cpp:119:8: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  119 |  main () {
      |        ^
#Verdict Execution timeMemoryGrader output
Fetching results...