Submission #3000659


Source Code Expand

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
#define MAXN 200010
int n, a[MAXN], Q, pre0[MAXN], pre1[MAXN], tree[MAXN << 2], tree2[MAXN << 2];
void getmin(int & a, int b) {if (a > b) a = b;}
struct Query {
	int l, r;
	inline bool operator < (const Query & b) const {return l == b.l ? r < b.r : l < b.l;}
	void read() {scanf("%d%d", &l, &r);}
} qs[MAXN];
void modify(int u, int l, int r, int tar, int v) {
	if (l == r) {
		tree[u] = v;
		tree2[u] = v - pre0[tar] + pre1[tar];
		return ;
	}
	int mid = l + r >> 1;
	if (tar <= mid) modify(u << 1, l, mid, tar, v);
	else modify(u << 1 | 1, mid + 1, r, tar, v);
	tree[u] = min(tree[u << 1], tree[u << 1 | 1]);
	tree2[u] = min(tree2[u << 1], tree2[u << 1 | 1]); 
}
int query(int u, int l, int r, int L, int R, int * tree) {
	if (L <= l && r <= R) return tree[u];
	int mid = l + r >> 1, res = 0x3f3f3f3f;
	if (L <= mid) getmin(res, query(u << 1, l, mid, L, R, tree));
	if (mid < R) getmin(res, query(u << 1 | 1, mid + 1, r, L, R, tree));
	return res;
}
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);
		pre0[i] = pre0[i - 1] + !a[i];
		pre1[i] = pre1[i - 1] + a[i];
	}
	scanf("%d", &Q);
	for (int i = 1; i <= Q; ++i) qs[i].read();
	sort(qs + 1, qs + 1 + Q);
	memset(tree, 0x3f, sizeof tree);
	memset(tree2, 0x3f, sizeof tree2);
	modify(1, 0, n, 0, pre1[n]);
	for (int i = 1; i <= Q; ++i) {
		int tx = min(	query(1, 0, n, 0, qs[i].l - 1, tree) - pre0[qs[i].l - 1] + pre1[qs[i].l - 1], 
						query(1, 0, n, qs[i].l, qs[i].r - 1, tree2))
				+ pre0[qs[i].r] - pre1[qs[i].r];
		getmin(tx, query(1, 0, n, qs[i].r, qs[i].r, tree));
		modify(1, 0, n, qs[i].r, tx);
	}
	printf("%d\n", query(1, 0, n, 0, n, tree));
	return 0;
}

Submission Info

Submission Time
Task F - NRE
User daklqw
Language C++ (GCC 5.4.1)
Score 1000
Code Size 1809 Byte
Status AC
Exec Time 238 ms
Memory 10368 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:34:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
./Main.cpp:36:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a[i]);
                     ^
./Main.cpp:40:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &Q);
                 ^
./Main.cpp: In member function ‘void Query::read()’:
./Main.cpp:12:36: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  void read() {scanf("%d%d", &l, &r);}
                                    ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 1000 / 1000
Status
AC × 7
AC × 127
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 218 ms 10368 KB
cent_1 AC 236 ms 10368 KB
cent_2 AC 208 ms 10368 KB
cent_3 AC 219 ms 10368 KB
cent_4 AC 221 ms 10368 KB
cent_5 AC 210 ms 10368 KB
cent_6 AC 219 ms 10368 KB
cent_7 AC 212 ms 10368 KB
cent_8 AC 230 ms 10368 KB
cent_9 AC 210 ms 10368 KB
example_0 AC 3 ms 6912 KB
example_1 AC 3 ms 6912 KB
example_2 AC 3 ms 6912 KB
example_3 AC 3 ms 6912 KB
example_4 AC 3 ms 6912 KB
example_5 AC 3 ms 6912 KB
example_6 AC 3 ms 6912 KB
full_0 AC 20 ms 8832 KB
full_1 AC 220 ms 10368 KB
full_10 AC 20 ms 8832 KB
full_11 AC 220 ms 10368 KB
full_12 AC 21 ms 8832 KB
full_13 AC 221 ms 10368 KB
full_14 AC 20 ms 8832 KB
full_15 AC 220 ms 10368 KB
full_16 AC 20 ms 8832 KB
full_17 AC 221 ms 10368 KB
full_18 AC 20 ms 8832 KB
full_19 AC 221 ms 10368 KB
full_2 AC 20 ms 8832 KB
full_3 AC 220 ms 10368 KB
full_4 AC 20 ms 8832 KB
full_5 AC 220 ms 10368 KB
full_6 AC 20 ms 8832 KB
full_7 AC 220 ms 10368 KB
full_8 AC 20 ms 8832 KB
full_9 AC 219 ms 10368 KB
maxrand_0 AC 21 ms 8832 KB
maxrand_1 AC 232 ms 10368 KB
maxrand_10 AC 21 ms 8832 KB
maxrand_11 AC 231 ms 10368 KB
maxrand_12 AC 21 ms 8832 KB
maxrand_13 AC 232 ms 10368 KB
maxrand_14 AC 20 ms 8832 KB
maxrand_15 AC 232 ms 10368 KB
maxrand_16 AC 21 ms 8832 KB
maxrand_17 AC 232 ms 10368 KB
maxrand_18 AC 21 ms 8832 KB
maxrand_19 AC 234 ms 10368 KB
maxrand_2 AC 20 ms 8832 KB
maxrand_20 AC 21 ms 8832 KB
maxrand_21 AC 238 ms 10368 KB
maxrand_22 AC 21 ms 8832 KB
maxrand_23 AC 235 ms 10368 KB
maxrand_24 AC 21 ms 8832 KB
maxrand_25 AC 232 ms 10368 KB
maxrand_26 AC 21 ms 8832 KB
maxrand_27 AC 235 ms 10368 KB
maxrand_28 AC 20 ms 8832 KB
maxrand_29 AC 234 ms 10368 KB
maxrand_3 AC 234 ms 10368 KB
maxrand_4 AC 20 ms 8832 KB
maxrand_5 AC 232 ms 10368 KB
maxrand_6 AC 20 ms 8832 KB
maxrand_7 AC 235 ms 10368 KB
maxrand_8 AC 20 ms 8832 KB
maxrand_9 AC 236 ms 10368 KB
rand_0 AC 234 ms 10368 KB
rand_1 AC 131 ms 8320 KB
rand_10 AC 234 ms 10368 KB
rand_11 AC 74 ms 8448 KB
rand_12 AC 234 ms 10368 KB
rand_13 AC 168 ms 9216 KB
rand_14 AC 233 ms 10368 KB
rand_15 AC 103 ms 8064 KB
rand_16 AC 232 ms 10368 KB
rand_17 AC 129 ms 8576 KB
rand_18 AC 234 ms 10368 KB
rand_19 AC 205 ms 9984 KB
rand_2 AC 233 ms 10368 KB
rand_3 AC 186 ms 8832 KB
rand_4 AC 233 ms 10368 KB
rand_5 AC 117 ms 8192 KB
rand_6 AC 232 ms 10368 KB
rand_7 AC 144 ms 8576 KB
rand_8 AC 232 ms 10368 KB
rand_9 AC 39 ms 8448 KB
small_0 AC 3 ms 6912 KB
small_1 AC 3 ms 6912 KB
small_2 AC 3 ms 6912 KB
small_3 AC 3 ms 6912 KB
small_4 AC 3 ms 6912 KB
small_5 AC 3 ms 6912 KB
small_6 AC 3 ms 6912 KB
small_7 AC 3 ms 6912 KB
small_8 AC 3 ms 6912 KB
small_9 AC 3 ms 6912 KB
smallwidth_0 AC 20 ms 8832 KB
smallwidth_1 AC 210 ms 10368 KB
smallwidth_10 AC 20 ms 8832 KB
smallwidth_11 AC 182 ms 10368 KB
smallwidth_12 AC 20 ms 8832 KB
smallwidth_13 AC 210 ms 10368 KB
smallwidth_14 AC 19 ms 8832 KB
smallwidth_15 AC 183 ms 10368 KB
smallwidth_16 AC 19 ms 8832 KB
smallwidth_17 AC 212 ms 10368 KB
smallwidth_18 AC 20 ms 8832 KB
smallwidth_19 AC 182 ms 10368 KB
smallwidth_2 AC 21 ms 8832 KB
smallwidth_20 AC 20 ms 8832 KB
smallwidth_21 AC 210 ms 10368 KB
smallwidth_22 AC 20 ms 8832 KB
smallwidth_23 AC 183 ms 10368 KB
smallwidth_24 AC 21 ms 8832 KB
smallwidth_25 AC 210 ms 10368 KB
smallwidth_26 AC 20 ms 8832 KB
smallwidth_27 AC 183 ms 10368 KB
smallwidth_28 AC 20 ms 8832 KB
smallwidth_29 AC 211 ms 10368 KB
smallwidth_3 AC 182 ms 10368 KB
smallwidth_4 AC 20 ms 8832 KB
smallwidth_5 AC 210 ms 10368 KB
smallwidth_6 AC 20 ms 8832 KB
smallwidth_7 AC 182 ms 10368 KB
smallwidth_8 AC 20 ms 8832 KB
smallwidth_9 AC 210 ms 10368 KB