Submission #3982277
Source Code Expand
#include <cstdio> #include <iostream> #include <string> #include <vector> #include <sstream> #include <map> #include <set> #include <queue> #include <algorithm> #include <cmath> #include <cstring> #include <typeinfo> #include <numeric> #include <functional> #include <unordered_map> #include <bitset> #include <stack> using namespace std; using ll = long long; using ull = unsigned long long; const ll INF = 1e16; const ll MOD = 1e9 + 7; #define REP(i, n) for(ll i = 0; i < n; i++) class SegmentTree { private: ll n; // 配列の要素数 ll s; // 配列を初期化するときの値 vector<ll> data; // セグメントツリーを持つ配列 public: SegmentTree(ll m, ll t); // mは配列の要素数、tは配列を初期化するときの値 ll operation(ll t1, ll t2); // 二項演算 void update(ll k, ll a); // k番目(0-indexed)の値をaに変更 ll query(ll a, ll b); // [a, b) の値を求める。 ll query(ll a, ll b, ll k, ll l, ll r); // [a, b) の値を求める。 }; SegmentTree::SegmentTree(ll m, ll t){ n = 1; while(n < m) n *= 2; data.assign(2 * n - 1, t); s = t; } ll SegmentTree::operation(ll t1, ll t2){ return min(t1, t2); } void SegmentTree::update(ll k, ll a){ k += n - 1; data[k] = a; while(k > 0){ k = (k - 1) / 2; data[k] = operation(data[k * 2 + 1], data[k * 2 + 2]); } } ll SegmentTree::query(ll a, ll b){ return query(a, b, 0, 0, n); } ll SegmentTree::query(ll a, ll b, ll k, ll l, ll r){ if(r <= a || b <= l) return s; if(a <= l && r <= b){ return data[k]; } else{ ll vl = query(a, b, k * 2 + 1, l, (l + r) / 2); ll vr = query(a, b, k * 2 + 2, (l + r) / 2, r); return operation(vl, vr); } } int main() { ll n; cin >> n; ll cnt = 0; vector<ll> b(n + 1); REP(i, n){ cin >> b[i + 1]; if(b[i + 1] == 0) cnt++; } ll q; cin >> q; vector<vector<ll>> v(n + 1); REP(i, q){ ll l, r; cin >> l >> r; v[l].push_back(r); } SegmentTree st(n + 1, INF); st.update(0, 0); for(ll i = 1; i <= n; i++){ sort(v[i].rbegin(), v[i].rend()); for(auto &r : v[i]){ ll res = st.query(i - 1, r); if(res < st.query(r, r + 1)) st.update(r, res); } ll res = st.query(i - 1, i) + (b[i]? 1 : -1); if(res < st.query(i, i + 1)) st.update(i, res); } cout << st.query(n, n + 1) + cnt << endl; }
Submission Info
Submission Time | |
---|---|
Task | F - NRE |
User | chocobo |
Language | C++14 (GCC 5.4.1) |
Score | 1000 |
Code Size | 2685 Byte |
Status | AC |
Exec Time | 392 ms |
Memory | 14848 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 1000 / 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 | AC | 368 ms | 13812 KB |
cent_1 | AC | 370 ms | 14464 KB |
cent_2 | AC | 352 ms | 13168 KB |
cent_3 | AC | 372 ms | 13944 KB |
cent_4 | AC | 362 ms | 14068 KB |
cent_5 | AC | 356 ms | 13296 KB |
cent_6 | AC | 373 ms | 13940 KB |
cent_7 | AC | 357 ms | 13684 KB |
cent_8 | AC | 376 ms | 14464 KB |
cent_9 | AC | 365 ms | 13296 KB |
example_0 | AC | 1 ms | 256 KB |
example_1 | AC | 1 ms | 256 KB |
example_2 | AC | 1 ms | 256 KB |
example_3 | AC | 1 ms | 256 KB |
example_4 | AC | 1 ms | 256 KB |
example_5 | AC | 1 ms | 256 KB |
example_6 | AC | 1 ms | 256 KB |
full_0 | AC | 115 ms | 10624 KB |
full_1 | AC | 360 ms | 14720 KB |
full_10 | AC | 116 ms | 10624 KB |
full_11 | AC | 361 ms | 14720 KB |
full_12 | AC | 117 ms | 10624 KB |
full_13 | AC | 362 ms | 14720 KB |
full_14 | AC | 116 ms | 10624 KB |
full_15 | AC | 362 ms | 14720 KB |
full_16 | AC | 116 ms | 10624 KB |
full_17 | AC | 362 ms | 14720 KB |
full_18 | AC | 116 ms | 10624 KB |
full_19 | AC | 365 ms | 14720 KB |
full_2 | AC | 116 ms | 10624 KB |
full_3 | AC | 361 ms | 14720 KB |
full_4 | AC | 116 ms | 10624 KB |
full_5 | AC | 364 ms | 14720 KB |
full_6 | AC | 117 ms | 10624 KB |
full_7 | AC | 371 ms | 14720 KB |
full_8 | AC | 116 ms | 10624 KB |
full_9 | AC | 362 ms | 14720 KB |
maxrand_0 | AC | 117 ms | 10624 KB |
maxrand_1 | AC | 376 ms | 14592 KB |
maxrand_10 | AC | 117 ms | 10624 KB |
maxrand_11 | AC | 374 ms | 14592 KB |
maxrand_12 | AC | 117 ms | 10624 KB |
maxrand_13 | AC | 374 ms | 14592 KB |
maxrand_14 | AC | 116 ms | 10624 KB |
maxrand_15 | AC | 375 ms | 14592 KB |
maxrand_16 | AC | 116 ms | 10624 KB |
maxrand_17 | AC | 374 ms | 14592 KB |
maxrand_18 | AC | 118 ms | 10624 KB |
maxrand_19 | AC | 373 ms | 14592 KB |
maxrand_2 | AC | 115 ms | 10624 KB |
maxrand_20 | AC | 116 ms | 10624 KB |
maxrand_21 | AC | 370 ms | 14592 KB |
maxrand_22 | AC | 118 ms | 10624 KB |
maxrand_23 | AC | 376 ms | 14592 KB |
maxrand_24 | AC | 117 ms | 10624 KB |
maxrand_25 | AC | 376 ms | 14592 KB |
maxrand_26 | AC | 117 ms | 10624 KB |
maxrand_27 | AC | 372 ms | 14592 KB |
maxrand_28 | AC | 116 ms | 10624 KB |
maxrand_29 | AC | 380 ms | 14592 KB |
maxrand_3 | AC | 371 ms | 14592 KB |
maxrand_4 | AC | 116 ms | 10624 KB |
maxrand_5 | AC | 379 ms | 14592 KB |
maxrand_6 | AC | 116 ms | 10624 KB |
maxrand_7 | AC | 373 ms | 14592 KB |
maxrand_8 | AC | 116 ms | 10624 KB |
maxrand_9 | AC | 392 ms | 14592 KB |
rand_0 | AC | 380 ms | 14592 KB |
rand_1 | AC | 179 ms | 5248 KB |
rand_10 | AC | 381 ms | 14592 KB |
rand_11 | AC | 142 ms | 7552 KB |
rand_12 | AC | 381 ms | 14592 KB |
rand_13 | AC | 274 ms | 11392 KB |
rand_14 | AC | 386 ms | 14592 KB |
rand_15 | AC | 141 ms | 4224 KB |
rand_16 | AC | 382 ms | 14592 KB |
rand_17 | AC | 196 ms | 7296 KB |
rand_18 | AC | 379 ms | 14592 KB |
rand_19 | AC | 329 ms | 13440 KB |
rand_2 | AC | 380 ms | 14592 KB |
rand_3 | AC | 243 ms | 5760 KB |
rand_4 | AC | 380 ms | 14592 KB |
rand_5 | AC | 141 ms | 2688 KB |
rand_6 | AC | 375 ms | 14592 KB |
rand_7 | AC | 208 ms | 7040 KB |
rand_8 | AC | 380 ms | 14592 KB |
rand_9 | AC | 117 ms | 9600 KB |
small_0 | AC | 1 ms | 256 KB |
small_1 | AC | 1 ms | 256 KB |
small_2 | AC | 1 ms | 256 KB |
small_3 | AC | 1 ms | 256 KB |
small_4 | AC | 1 ms | 256 KB |
small_5 | AC | 1 ms | 256 KB |
small_6 | AC | 1 ms | 256 KB |
small_7 | AC | 1 ms | 256 KB |
small_8 | AC | 1 ms | 256 KB |
small_9 | AC | 1 ms | 256 KB |
smallwidth_0 | AC | 115 ms | 10624 KB |
smallwidth_1 | AC | 355 ms | 14848 KB |
smallwidth_10 | AC | 115 ms | 10624 KB |
smallwidth_11 | AC | 331 ms | 14848 KB |
smallwidth_12 | AC | 117 ms | 10624 KB |
smallwidth_13 | AC | 357 ms | 14848 KB |
smallwidth_14 | AC | 115 ms | 10624 KB |
smallwidth_15 | AC | 330 ms | 14848 KB |
smallwidth_16 | AC | 115 ms | 10624 KB |
smallwidth_17 | AC | 357 ms | 14848 KB |
smallwidth_18 | AC | 116 ms | 10624 KB |
smallwidth_19 | AC | 333 ms | 14848 KB |
smallwidth_2 | AC | 117 ms | 10624 KB |
smallwidth_20 | AC | 116 ms | 10624 KB |
smallwidth_21 | AC | 355 ms | 14848 KB |
smallwidth_22 | AC | 116 ms | 10624 KB |
smallwidth_23 | AC | 331 ms | 14848 KB |
smallwidth_24 | AC | 116 ms | 10624 KB |
smallwidth_25 | AC | 356 ms | 14848 KB |
smallwidth_26 | AC | 115 ms | 10624 KB |
smallwidth_27 | AC | 333 ms | 14848 KB |
smallwidth_28 | AC | 116 ms | 10624 KB |
smallwidth_29 | AC | 355 ms | 14848 KB |
smallwidth_3 | AC | 338 ms | 14848 KB |
smallwidth_4 | AC | 116 ms | 10624 KB |
smallwidth_5 | AC | 378 ms | 14848 KB |
smallwidth_6 | AC | 116 ms | 10624 KB |
smallwidth_7 | AC | 333 ms | 14848 KB |
smallwidth_8 | AC | 116 ms | 10624 KB |
smallwidth_9 | AC | 359 ms | 14848 KB |