oj.uz

Submission #406290

# Submission time Handle Problem Language Result Execution time Memory
406290 2021-05-17T10:29:59 Z Kevin_Zhang_TW Election (BOI18_election) C++17
100 / 100
 936 ms 50932 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif

const int MAX_N = 500010;

int n, q;
char w[MAX_N];
int lp[MAX_N], mar[MAX_N], ql[MAX_N], qr[MAX_N];
int res[MAX_N];

vector<pair<int,int>> allq[MAX_N];

bool ban[MAX_N];

// bit tree1
// sgt tree2

struct bit {
	int n;
	vector<int> v;
	bit (int _n) {
		n = _n + 10;
		v.resize(n);
	}
	void add(int i, int val) {
		for (++i;i <= n;i += i&-i)
			v[i] += val;
	}
	int qry(int i) {
		int res = 0;
		for (++i;i;i ^= i&-i) 
			res += v[i];
		return res;
	}
	int qry(int l, int r) { return qry(r) - qry(l-1); }
};
struct sgt {
	struct node {
		int mn, at;
		node () : mn(0), at(0) {}
		void operator += (int v) {
			mn += v, at += v;
		}
		node (node a, node b) {
			mn = min(a.mn, b.mn);
			at = 0;
		}
	};
	int n;
	vector<node> val;
	sgt (int _n) {
		n = _n;
		val.resize(n<<1);
	}
	void push(int i) {
		if (i >= n) return;
		int &at = val[i].at;
		val[i<<1] += at, val[i<<1|1] += at;
		at = 0;
	}
	void upd(int i) {
		if (i >= n) return;
		push(i);
		val[i] = node(val[i<<1], val[i<<1|1]);
	}
	void add(int l, int r, int v) {
		DE(l, r, v);
		int sl = l += n, sr = r += n;
		for (;l < r;l>>=1, r>>=1) {
			if (l&1) val[l++] += v;
			if (r&1) val[--r] += v;
		}
		for (;sl>>=1, sr>>=1;)
			upd(sl), upd(sr);
	}
	int qry(int l, int r) {
		if (l == r) return 0;
		int res = n;
		l += n, r += n;
		for (int i = 20;i > 0;--i) push(l>>i), push(r>>i);
		for (;l < r;l>>=1, r>>=1) {
			if (l&1) chmin(res, val[l++].mn);
			if (r&1) chmin(res, val[--r].mn);
		}
		return res;
	}
};
void solve() {

	bit tree1(n);
	sgt tree2(n);

	for (int i = 0;i < n;++i) {
		if (ban[i]) {
			tree1.add(i, 1);
			continue;
		}
		DE(i, w[i]);
		if (w[i] == 'T') {
			tree2.add(0, i+1, -1);
		}
		if (w[i] == 'C') {
			tree2.add(0, i+1, 1);
		}
	}
	for (int i = 0;i < n;++i) DE(i, tree2.qry(i, i+1));

	for (int i = 0;i < n;++i) {
		for (auto [r, id] : allq[i]) {
			DE(i, r, tree2.qry(r+1, r+2), tree2.qry(i, r+1));
			res[id] = tree1.qry(i, r);
			int suf = tree2.qry(r+1, r+2);
			res[id] += max(0, suf - tree2.qry(i, r+1));
		}
		if (mar[i] == -1) continue;
		int j = mar[i];
		ban[j] = true;
		tree1.add(j, 1);
		tree2.add(0, j+1, 1);
	}
}

int32_t main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> n >> w;
	{
		vector<int> stk{-1};
		fill(mar, mar + n, -1);
		for (int i = 0;i < n;++i) {
			lp[i] = i;
			if (w[i] == 'C')
				stk.pb(i);
			if (w[i] == 'T') {
				lp[i] = stk.back();
				if (lp[i] == -1) {
					ban[i] = true;
					continue;
				}
				mar[ lp[i] ] = i;
				stk.pop_back();
			}
		}
	}
	cin >> q;
	for (int i = 0;i < q;++i) {
		cin >> ql[i] >> qr[i], --ql[i], --qr[i];
		allq[ ql[i] ].pb( qr[i], i);
	}

	solve();

	for (int i = 0;i < q;++i)
		cout << res[i] << '\n';
}

Compilation message

election.cpp: In member function 'void sgt::add(int, int, int)':
election.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
election.cpp:81:3: note: in expansion of macro 'DE'
   81 |   DE(l, r, v);
      |   ^~
election.cpp: In function 'void solve()':
election.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
election.cpp:112:3: note: in expansion of macro 'DE'
  112 |   DE(i, w[i]);
      |   ^~
election.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
election.cpp:120:28: note: in expansion of macro 'DE'
  120 |  for (int i = 0;i < n;++i) DE(i, tree2.qry(i, i+1));
      |                            ^~
election.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
election.cpp:124:4: note: in expansion of macro 'DE'
  124 |    DE(i, r, tree2.qry(r+1, r+2), tree2.qry(i, r+1));
      |    ^~

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12236 KB Output is correct
2 Correct 11 ms 12200 KB Output is correct
3 Correct 13 ms 12236 KB Output is correct
4 Correct 11 ms 12236 KB Output is correct
5 Correct 12 ms 12260 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12236 KB Output is correct
2 Correct 11 ms 12200 KB Output is correct
3 Correct 13 ms 12236 KB Output is correct
4 Correct 11 ms 12236 KB Output is correct
5 Correct 12 ms 12260 KB Output is correct
6 Correct 102 ms 17368 KB Output is correct
7 Correct 94 ms 16804 KB Output is correct
8 Correct 111 ms 16920 KB Output is correct
9 Correct 106 ms 17240 KB Output is correct
10 Correct 107 ms 17368 KB Output is correct
11 Correct 97 ms 17392 KB Output is correct
12 Correct 107 ms 17284 KB Output is correct
13 Correct 91 ms 17392 KB Output is correct
14 Correct 96 ms 17348 KB Output is correct
15 Correct 99 ms 17352 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12236 KB Output is correct
2 Correct 11 ms 12200 KB Output is correct
3 Correct 13 ms 12236 KB Output is correct
4 Correct 11 ms 12236 KB Output is correct
5 Correct 12 ms 12260 KB Output is correct
6 Correct 102 ms 17368 KB Output is correct
7 Correct 94 ms 16804 KB Output is correct
8 Correct 111 ms 16920 KB Output is correct
9 Correct 106 ms 17240 KB Output is correct
10 Correct 107 ms 17368 KB Output is correct
11 Correct 97 ms 17392 KB Output is correct
12 Correct 107 ms 17284 KB Output is correct
13 Correct 91 ms 17392 KB Output is correct
14 Correct 96 ms 17348 KB Output is correct
15 Correct 99 ms 17352 KB Output is correct
16 Correct 903 ms 50852 KB Output is correct
17 Correct 708 ms 46788 KB Output is correct
18 Correct 794 ms 47956 KB Output is correct
19 Correct 852 ms 50064 KB Output is correct
20 Correct 887 ms 50820 KB Output is correct
21 Correct 869 ms 50916 KB Output is correct
22 Correct 903 ms 50932 KB Output is correct
23 Correct 822 ms 50900 KB Output is correct
24 Correct 936 ms 50660 KB Output is correct
25 Correct 885 ms 50628 KB Output is correct