Submission #5558763
Source Code Expand
#include <iostream> #include <fstream> #include <cstdio> #include <cmath> #include <vector> #include <string> #include <set> #include <map> #include <stack> #include <queue> #include <deque> #include <bitset> #include <algorithm> #include <complex> #include <array> using namespace std; #define REP(i,n) for(int i=0; i<n; ++i) #define FOR(i,a,b) for(int i=a; i<=b; ++i) #define FORR(i,a,b) for (int i=a; i>=b; --i) #define ALL(c) (c).begin(), (c).end() typedef long long ll; typedef vector<int> VI; typedef vector<ll> VL; typedef vector<VI> VVI; typedef vector<VL> VVL; typedef pair<int,int> P; typedef pair<ll,ll> PL; typedef vector<double> VD; typedef vector<VD> VVD; template<typename T> void chmin(T &a, T b) { if (a > b) a = b; } template<typename T> void chmax(T &a, T b) { if (a < b) a = b; } int in() { int x; scanf("%d", &x); return x; } ll lin() { ll x; scanf("%lld", &x); return x; } struct SegmentTree{ const int INF = 1e9; int n, width; VI dat; void init(int x){ n = x; width = 1; while (width < n) width *= 2; dat.resize(2*width-1); REP(i,2*width-1) dat[i] = INF; } void update(int i, int x){ i += width - 1; chmin(dat[i], x); // dat[i] = x; while (i > 0){ i = (i - 1) / 2; dat[i] = min(dat[i*2+1], dat[i*2+2]); } } int query(int a, int b, int k, int l, int r){ if (r <= a || b <= l) return INF; if (a <= l && r <= b) return dat[k]; int vl = query(a, b, k*2+1, l, (l+r)/2); int vr = query(a, b, k*2+2, (l+r)/2, r); return min(vl, vr); } // [l, r) int query(int l, int r){ return query(l, r, 0, 0, width); } }; int main() { int n; cin >> n; VI a(n), s0(n + 1), s1(n + 1); REP(i,n){ a[i] = in(); s0[i + 1] = s0[i] + (a[i] == 0); s1[i + 1] = s1[i] + (a[i] == 1); } int q; cin >> q; VVI r(n); REP(i,q){ int x = in() - 1, y = in(); r[x].push_back(y); } SegmentTree seg0, seg1; seg0.init(n + 1); seg1.init(n + 1); seg0.update(0, 0); seg1.update(0, 0); REP(i,n){ for (int x : r[i]){ int d = min( seg0.query(0, i) + s1[i] + s0[x] - s0[i], seg1.query(i, x) + s0[x] ); seg0.update(x, d - s1[x]); seg1.update(x, d - s0[x]); } } int ans = seg0.query(0, n + 1) + s1[n]; cout << ans << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | F - NRE |
User | TangentDay |
Language | C++14 (GCC 5.4.1) |
Score | 1000 |
Code Size | 2650 Byte |
Status | AC |
Exec Time | 195 ms |
Memory | 15360 KB |
Compile Error
./Main.cpp: In function ‘int in()’: ./Main.cpp:36:34: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] int in() { int x; scanf("%d", &x); return x; } ^ ./Main.cpp: In function ‘ll lin()’: ./Main.cpp:37:35: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] ll lin() { ll x; scanf("%lld", &x); return x; } ^
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 | 171 ms | 14072 KB |
cent_1 | AC | 189 ms | 14848 KB |
cent_2 | AC | 162 ms | 13428 KB |
cent_3 | AC | 172 ms | 14332 KB |
cent_4 | AC | 170 ms | 14456 KB |
cent_5 | AC | 163 ms | 13556 KB |
cent_6 | AC | 170 ms | 14328 KB |
cent_7 | AC | 165 ms | 13944 KB |
cent_8 | AC | 176 ms | 14976 KB |
cent_9 | AC | 164 ms | 13556 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 | 23 ms | 11392 KB |
full_1 | AC | 173 ms | 15232 KB |
full_10 | AC | 24 ms | 11392 KB |
full_11 | AC | 173 ms | 15232 KB |
full_12 | AC | 24 ms | 11392 KB |
full_13 | AC | 172 ms | 15232 KB |
full_14 | AC | 23 ms | 11392 KB |
full_15 | AC | 173 ms | 15232 KB |
full_16 | AC | 23 ms | 11392 KB |
full_17 | AC | 176 ms | 15232 KB |
full_18 | AC | 23 ms | 11392 KB |
full_19 | AC | 177 ms | 15232 KB |
full_2 | AC | 24 ms | 11392 KB |
full_3 | AC | 176 ms | 15232 KB |
full_4 | AC | 24 ms | 11392 KB |
full_5 | AC | 180 ms | 15232 KB |
full_6 | AC | 23 ms | 11392 KB |
full_7 | AC | 182 ms | 15232 KB |
full_8 | AC | 23 ms | 11392 KB |
full_9 | AC | 175 ms | 15232 KB |
maxrand_0 | AC | 24 ms | 11392 KB |
maxrand_1 | AC | 181 ms | 14976 KB |
maxrand_10 | AC | 24 ms | 11392 KB |
maxrand_11 | AC | 181 ms | 14976 KB |
maxrand_12 | AC | 24 ms | 11392 KB |
maxrand_13 | AC | 183 ms | 14976 KB |
maxrand_14 | AC | 24 ms | 11392 KB |
maxrand_15 | AC | 180 ms | 14976 KB |
maxrand_16 | AC | 23 ms | 11392 KB |
maxrand_17 | AC | 179 ms | 14976 KB |
maxrand_18 | AC | 25 ms | 11392 KB |
maxrand_19 | AC | 182 ms | 14976 KB |
maxrand_2 | AC | 23 ms | 11392 KB |
maxrand_20 | AC | 24 ms | 11392 KB |
maxrand_21 | AC | 195 ms | 14976 KB |
maxrand_22 | AC | 25 ms | 11392 KB |
maxrand_23 | AC | 187 ms | 14976 KB |
maxrand_24 | AC | 24 ms | 11392 KB |
maxrand_25 | AC | 178 ms | 14976 KB |
maxrand_26 | AC | 23 ms | 11392 KB |
maxrand_27 | AC | 180 ms | 14976 KB |
maxrand_28 | AC | 23 ms | 11392 KB |
maxrand_29 | AC | 185 ms | 14976 KB |
maxrand_3 | AC | 183 ms | 14976 KB |
maxrand_4 | AC | 23 ms | 11392 KB |
maxrand_5 | AC | 186 ms | 14976 KB |
maxrand_6 | AC | 24 ms | 11392 KB |
maxrand_7 | AC | 187 ms | 14976 KB |
maxrand_8 | AC | 25 ms | 11392 KB |
maxrand_9 | AC | 184 ms | 14976 KB |
rand_0 | AC | 187 ms | 14976 KB |
rand_1 | AC | 95 ms | 4864 KB |
rand_10 | AC | 181 ms | 14976 KB |
rand_11 | AC | 63 ms | 7936 KB |
rand_12 | AC | 185 ms | 14976 KB |
rand_13 | AC | 130 ms | 11520 KB |
rand_14 | AC | 183 ms | 14976 KB |
rand_15 | AC | 76 ms | 3840 KB |
rand_16 | AC | 181 ms | 14976 KB |
rand_17 | AC | 98 ms | 7296 KB |
rand_18 | AC | 181 ms | 14976 KB |
rand_19 | AC | 155 ms | 13824 KB |
rand_2 | AC | 181 ms | 14976 KB |
rand_3 | AC | 132 ms | 4992 KB |
rand_4 | AC | 180 ms | 14976 KB |
rand_5 | AC | 78 ms | 1792 KB |
rand_6 | AC | 188 ms | 14976 KB |
rand_7 | AC | 107 ms | 6784 KB |
rand_8 | AC | 178 ms | 14976 KB |
rand_9 | AC | 36 ms | 10240 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 | 23 ms | 11392 KB |
smallwidth_1 | AC | 163 ms | 15360 KB |
smallwidth_10 | AC | 22 ms | 11392 KB |
smallwidth_11 | AC | 142 ms | 15360 KB |
smallwidth_12 | AC | 23 ms | 11392 KB |
smallwidth_13 | AC | 164 ms | 15360 KB |
smallwidth_14 | AC | 22 ms | 11392 KB |
smallwidth_15 | AC | 143 ms | 15360 KB |
smallwidth_16 | AC | 23 ms | 11392 KB |
smallwidth_17 | AC | 165 ms | 15360 KB |
smallwidth_18 | AC | 23 ms | 11392 KB |
smallwidth_19 | AC | 149 ms | 15360 KB |
smallwidth_2 | AC | 24 ms | 11392 KB |
smallwidth_20 | AC | 24 ms | 11392 KB |
smallwidth_21 | AC | 163 ms | 15360 KB |
smallwidth_22 | AC | 23 ms | 11392 KB |
smallwidth_23 | AC | 144 ms | 15360 KB |
smallwidth_24 | AC | 24 ms | 11392 KB |
smallwidth_25 | AC | 166 ms | 15360 KB |
smallwidth_26 | AC | 23 ms | 11392 KB |
smallwidth_27 | AC | 143 ms | 15360 KB |
smallwidth_28 | AC | 23 ms | 11392 KB |
smallwidth_29 | AC | 163 ms | 15360 KB |
smallwidth_3 | AC | 143 ms | 15360 KB |
smallwidth_4 | AC | 23 ms | 11392 KB |
smallwidth_5 | AC | 163 ms | 15360 KB |
smallwidth_6 | AC | 23 ms | 11392 KB |
smallwidth_7 | AC | 143 ms | 15360 KB |
smallwidth_8 | AC | 23 ms | 11392 KB |
smallwidth_9 | AC | 163 ms | 15360 KB |