oj.uz

Submission #295429

# Submission time Handle Problem Language Result Execution time Memory
295429 2020-09-09T16:39:08 Z spdskatr Monochrome Points (JOI20_monochrome) C++14
0 / 100
 1 ms 384 KB 
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cassert>
#include <cstring>
#define SZ (1<<12)

using namespace std;

int N;
int col[200005], sa[2005], sb[2005], ans, resa[2005], resb[2005];
vector<int> bws, bbs;

int inter(int a, int b) {
	int l1 = resa[a], r1 = resb[a];
	if (l1 > r1) swap(l1, r1);
	int l2 = resa[b], r2 = resb[b];
	if (l2 > r2) swap(l2, r2);
	//printf("inter [%d, %d] with [%d, %d]\n", l1, r1, l2, r2);
	return (l1 < l2 && l2 < r1 && r1 < r2) || (l1 > l2 && r2 > l1 && r1 > r2);
}

struct Segtree {
	int st[(1<<13)];
	void reset() {
		memset(st, 0, sizeof(st));
	}
	void seg_inc(int i, int v) {
		for (st[i += SZ] += v; i > 1; i >>= 1) st[i>>1] = st[i] + st[i^1];
	}
	int seg_q(int l, int r) {
		int res = 0;
		for (l += SZ, r += SZ; l < r; l >>= 1, r >>= 1) {
			if (l&1) res += st[l++];
			if (r&1) res += st[--r];
		}
		return res;
	}
} st1;

int main() {
	scanf("%d", &N);
	assert(N <= 2000);
	for (int i = 0; i < 2*N; i++) {
		char op;
		scanf(" %c", &op);
		if (op == 'B') col[i] = 1;
	}
	for (int i = 0; i < 2; i++) {
		bws.clear();
		bbs.clear();
		st1.reset();
		for (int j = 0; j < N; j++) {
			sa[j] = col[i+j];
			sb[j] = col[(i+j+N)%(2*N)];
			if (sb[j]) bbs.push_back(j);
			else bws.push_back(j);
		}
		reverse(bws.begin(), bws.end());
		reverse(bbs.begin(), bbs.end());
		for (int j = 0; j < N; j++) {
			resa[j] = j;
			if (sa[j]) {
				resb[j] = bws.back();
				bws.pop_back();
			} else {
				resb[j] = bbs.back();
				bbs.pop_back();
			}
		}
		int cnt = 0;
		for (int j = 0; j < N; j++) {
			cnt += st1.seg_q(0, resb[j]);
			st1.seg_inc(resb[j], 1);
		}
		ans = max(ans, cnt);
	}
	printf("%d\n", ans);
}

Compilation message

monochrome.cpp: In function 'int main()':
monochrome.cpp:43:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   43 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
monochrome.cpp:47:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   47 |   scanf(" %c", &op);
      |   ~~~~~^~~~~~~~~~~~

Subtask #1
0.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Incorrect 1 ms 384 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Incorrect 1 ms 384 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Incorrect 1 ms 384 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Incorrect 1 ms 384 KB Output isn't correct
10 Halted 0 ms 0 KB -