Submission #3995753
Source Code Expand
#include<bits/stdc++.h> using namespace std; #define lol(i,n) for(int i=0;i<n;i++) #define chmax(a,b) a=max(a,b); typedef long long ll; #define N 200010 class RAQxRMQ { private: ll dat[2 * N], laz[2 * N]; ll eval(ll k) { if (k < N) { laz[k * 2] += laz[k]; laz[k * 2 + 1] += laz[k]; } dat[k] += laz[k],laz[k]=0; return dat[k]; } public: void init() { lol(i, 2 * N)dat[i] = -1e17, laz[i] = 0; } void add(ll l, ll r, ll x) { l += N, r += N + 1; for (ll a = l, b = r; a < b; a >>= 1, b >>= 1) { if (a & 1)laz[a++] += x; if (b & 1)laz[--b] += x; } for (ll a = l, b = r; a + b; a >>= 1, b >>= 1) { dat[a / 2] = max(eval(a), eval(a ^ 1)); dat[b / 2] = max(eval(b), eval(b ^ 1)); } } ll maxi(ll l, ll r) { l += N, r += N + 1; for (ll d = 20; ~d; d--) { eval(l >> d); eval(r >> d); } ll res = -1e18; for (ll a = l, b = r; a < b; a >>= 1, b >>= 1) { if (a & 1)chmax(res, eval(a++)); if (b & 1)chmax(res, eval(--b)); } return res; } void upd(ll i, ll x) { ll val = maxi(i, i); add(i, i, max(0LL,x-val)); } }; ll n, d[N], q; vector<ll> v[N]; int main() { cin >> n; lol(i, n)scanf("%lld",&d[i]); cin >> q; lol(i, q) { ll a, b; scanf("%lld%lld", &a, &b); a--; v[a].push_back(b); } RAQxRMQ seg; seg.init(); seg.upd(0, 0); lol(i, n) { sort(v[i].begin(), v[i].end()); for (auto to : v[i]) { seg.upd(to, seg.maxi(0, to - 1)); } ll val = (d[i] == 0 ? -1 : +1); seg.add(i +1, n+1, val); } ll ans = -seg.maxi(0, n+1); lol(i, n)ans += d[i]; cout << ans+1 << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | F - NRE |
User | luogu_bot4 |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1634 Byte |
Status | WA |
Exec Time | 248 ms |
Memory | 16896 KB |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:54:30: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] lol(i, n)scanf("%lld",&d[i]); ^ ./Main.cpp:57:37: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] ll a, b; scanf("%lld%lld", &a, &b); a--; ^
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 1000 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | example_0, example_1, example_2, example_3, example_4, example_5, example_6 |
All | cent_0, cent_1, cent_2, cent_3, cent_4, cent_5, cent_6, cent_7, cent_8, cent_9, example_0, example_1, example_2, example_3, example_4, example_5, example_6, full_0, full_1, full_10, full_11, full_12, full_13, full_14, full_15, full_16, full_17, full_18, full_19, full_2, full_3, full_4, full_5, full_6, full_7, full_8, full_9, maxrand_0, maxrand_1, maxrand_10, maxrand_11, maxrand_12, maxrand_13, maxrand_14, maxrand_15, maxrand_16, maxrand_17, maxrand_18, maxrand_19, maxrand_2, maxrand_20, maxrand_21, maxrand_22, maxrand_23, maxrand_24, maxrand_25, maxrand_26, maxrand_27, maxrand_28, maxrand_29, maxrand_3, maxrand_4, maxrand_5, maxrand_6, maxrand_7, maxrand_8, maxrand_9, rand_0, rand_1, rand_10, rand_11, rand_12, rand_13, rand_14, rand_15, rand_16, rand_17, rand_18, rand_19, rand_2, rand_3, rand_4, rand_5, rand_6, rand_7, rand_8, rand_9, small_0, small_1, small_2, small_3, small_4, small_5, small_6, small_7, small_8, small_9, smallwidth_0, smallwidth_1, smallwidth_10, smallwidth_11, smallwidth_12, smallwidth_13, smallwidth_14, smallwidth_15, smallwidth_16, smallwidth_17, smallwidth_18, smallwidth_19, smallwidth_2, smallwidth_20, smallwidth_21, smallwidth_22, smallwidth_23, smallwidth_24, smallwidth_25, smallwidth_26, smallwidth_27, smallwidth_28, smallwidth_29, smallwidth_3, smallwidth_4, smallwidth_5, smallwidth_6, smallwidth_7, smallwidth_8, smallwidth_9 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
cent_0 | WA | 239 ms | 15988 KB |
cent_1 | WA | 241 ms | 16640 KB |
cent_2 | WA | 236 ms | 15344 KB |
cent_3 | WA | 239 ms | 16120 KB |
cent_4 | WA | 234 ms | 16244 KB |
cent_5 | WA | 228 ms | 15472 KB |
cent_6 | WA | 234 ms | 16116 KB |
cent_7 | WA | 226 ms | 15860 KB |
cent_8 | WA | 232 ms | 16640 KB |
cent_9 | WA | 226 ms | 15472 KB |
example_0 | WA | 7 ms | 12672 KB |
example_1 | WA | 7 ms | 12672 KB |
example_2 | WA | 7 ms | 12672 KB |
example_3 | WA | 7 ms | 12672 KB |
example_4 | WA | 7 ms | 12672 KB |
example_5 | WA | 7 ms | 12672 KB |
example_6 | WA | 7 ms | 12672 KB |
full_0 | WA | 71 ms | 12800 KB |
full_1 | WA | 240 ms | 16896 KB |
full_10 | WA | 71 ms | 12800 KB |
full_11 | WA | 233 ms | 16896 KB |
full_12 | WA | 71 ms | 12800 KB |
full_13 | WA | 232 ms | 16896 KB |
full_14 | WA | 70 ms | 12800 KB |
full_15 | WA | 232 ms | 16896 KB |
full_16 | WA | 71 ms | 12800 KB |
full_17 | WA | 243 ms | 16896 KB |
full_18 | WA | 72 ms | 12800 KB |
full_19 | WA | 231 ms | 16896 KB |
full_2 | WA | 71 ms | 12800 KB |
full_3 | WA | 231 ms | 16896 KB |
full_4 | WA | 71 ms | 12800 KB |
full_5 | WA | 237 ms | 16896 KB |
full_6 | WA | 70 ms | 12800 KB |
full_7 | WA | 248 ms | 16896 KB |
full_8 | WA | 70 ms | 12800 KB |
full_9 | WA | 230 ms | 16896 KB |
maxrand_0 | WA | 71 ms | 12800 KB |
maxrand_1 | WA | 235 ms | 16768 KB |
maxrand_10 | WA | 71 ms | 12800 KB |
maxrand_11 | WA | 234 ms | 16640 KB |
maxrand_12 | WA | 72 ms | 12800 KB |
maxrand_13 | WA | 238 ms | 16640 KB |
maxrand_14 | WA | 71 ms | 12800 KB |
maxrand_15 | WA | 231 ms | 16640 KB |
maxrand_16 | WA | 70 ms | 12800 KB |
maxrand_17 | WA | 232 ms | 16640 KB |
maxrand_18 | WA | 71 ms | 12800 KB |
maxrand_19 | WA | 239 ms | 16640 KB |
maxrand_2 | WA | 71 ms | 12800 KB |
maxrand_20 | WA | 71 ms | 12800 KB |
maxrand_21 | WA | 234 ms | 16640 KB |
maxrand_22 | WA | 72 ms | 12800 KB |
maxrand_23 | WA | 233 ms | 16640 KB |
maxrand_24 | WA | 71 ms | 12800 KB |
maxrand_25 | WA | 234 ms | 16640 KB |
maxrand_26 | WA | 72 ms | 12800 KB |
maxrand_27 | WA | 234 ms | 16640 KB |
maxrand_28 | WA | 70 ms | 12800 KB |
maxrand_29 | WA | 241 ms | 16640 KB |
maxrand_3 | WA | 234 ms | 16640 KB |
maxrand_4 | WA | 71 ms | 12800 KB |
maxrand_5 | WA | 232 ms | 16640 KB |
maxrand_6 | WA | 70 ms | 12800 KB |
maxrand_7 | WA | 242 ms | 16640 KB |
maxrand_8 | WA | 70 ms | 12800 KB |
maxrand_9 | WA | 248 ms | 16640 KB |
rand_0 | WA | 236 ms | 16768 KB |
rand_1 | WA | 125 ms | 14848 KB |
rand_10 | WA | 233 ms | 16640 KB |
rand_11 | WA | 92 ms | 14080 KB |
rand_12 | WA | 232 ms | 16640 KB |
rand_13 | WA | 173 ms | 15488 KB |
rand_14 | WA | 233 ms | 16640 KB |
rand_15 | WA | 98 ms | 14336 KB |
rand_16 | WA | 240 ms | 16768 KB |
rand_17 | WA | 130 ms | 14848 KB |
rand_18 | WA | 232 ms | 16640 KB |
rand_19 | WA | 213 ms | 16128 KB |
rand_2 | WA | 233 ms | 16640 KB |
rand_3 | WA | 167 ms | 15616 KB |
rand_4 | WA | 245 ms | 16640 KB |
rand_5 | WA | 112 ms | 14720 KB |
rand_6 | WA | 232 ms | 16640 KB |
rand_7 | WA | 140 ms | 14976 KB |
rand_8 | WA | 243 ms | 16640 KB |
rand_9 | WA | 72 ms | 13312 KB |
small_0 | WA | 7 ms | 12672 KB |
small_1 | WA | 7 ms | 12672 KB |
small_2 | WA | 7 ms | 12672 KB |
small_3 | WA | 7 ms | 12672 KB |
small_4 | WA | 7 ms | 12672 KB |
small_5 | WA | 7 ms | 12672 KB |
small_6 | WA | 7 ms | 12672 KB |
small_7 | WA | 7 ms | 12672 KB |
small_8 | WA | 6 ms | 12672 KB |
small_9 | WA | 7 ms | 12672 KB |
smallwidth_0 | WA | 70 ms | 12928 KB |
smallwidth_1 | WA | 229 ms | 16896 KB |
smallwidth_10 | WA | 71 ms | 12800 KB |
smallwidth_11 | WA | 224 ms | 16896 KB |
smallwidth_12 | WA | 73 ms | 12800 KB |
smallwidth_13 | WA | 231 ms | 16896 KB |
smallwidth_14 | WA | 70 ms | 12800 KB |
smallwidth_15 | WA | 229 ms | 16896 KB |
smallwidth_16 | WA | 70 ms | 12800 KB |
smallwidth_17 | WA | 240 ms | 16896 KB |
smallwidth_18 | WA | 70 ms | 12800 KB |
smallwidth_19 | WA | 221 ms | 16896 KB |
smallwidth_2 | WA | 71 ms | 12800 KB |
smallwidth_20 | WA | 71 ms | 12800 KB |
smallwidth_21 | WA | 231 ms | 16896 KB |
smallwidth_22 | WA | 71 ms | 12800 KB |
smallwidth_23 | WA | 222 ms | 16896 KB |
smallwidth_24 | WA | 71 ms | 12800 KB |
smallwidth_25 | WA | 242 ms | 16896 KB |
smallwidth_26 | WA | 71 ms | 12800 KB |
smallwidth_27 | WA | 224 ms | 16896 KB |
smallwidth_28 | WA | 71 ms | 12800 KB |
smallwidth_29 | WA | 230 ms | 16896 KB |
smallwidth_3 | WA | 222 ms | 16896 KB |
smallwidth_4 | WA | 70 ms | 12800 KB |
smallwidth_5 | WA | 229 ms | 16896 KB |
smallwidth_6 | WA | 70 ms | 12800 KB |
smallwidth_7 | WA | 222 ms | 16896 KB |
smallwidth_8 | WA | 70 ms | 12800 KB |
smallwidth_9 | WA | 231 ms | 16896 KB |