oj.uz

Submission #87766

# Submission time Handle Problem Language Result Execution time Memory
87766 2018-12-02T10:35:47 Z memikakizaki Election (BOI18_election) C++14
28 / 100
 3000 ms 2136 KB 
#include <bits/stdc++.h>
using namespace std;
#define long long long
const long MOD = 1e9+7, LINF = 1e18 + 1e16;
const int INF = 1e9+1;
const double EPS = 1e-10;
const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
const int N = 5e5+1;

class ElectionsBruteForce {

	int n, q;
	string s;

public:
	void run(istream &cin, ostream &cout) {
		cin >> n >> s >> q;
		for(int i = 0, l, r; i < q; i++) {
			cin >> l >> r;
			--l, --r;
			vector<bool> mark(n);
			int cnt = 0, curr = 0;
			for(int j = l; j <= r; j++) {
				if(curr + (s[j] == 'C' ? 1 : -1) < 0) {
					mark[j] = true;
					++cnt;
				} else curr += (s[j] == 'C' ? 1 : -1);
			}
			curr = 0;
			for(int j = r; j >= l; j--) if(!mark[j]) {
				if(curr + (s[j] == 'C' ? 1 : -1) < 0) mark[j] = true, ++cnt;
				else curr += (s[j] == 'C' ? 1 : -1);
			}
			cout << cnt << '\n';
		}
	}
};


class Solver {
public:
	void solve(std::istream& in, std::ostream& out) {
	    ElectionsBruteForce *obj = new ElectionsBruteForce();
		obj->run(in, out);
	}
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	Solver solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 376 KB Output is correct
2 Correct 8 ms 604 KB Output is correct
3 Correct 7 ms 712 KB Output is correct
4 Correct 8 ms 784 KB Output is correct
5 Correct 7 ms 784 KB Output is correct

Subtask #2
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 376 KB Output is correct
2 Correct 8 ms 604 KB Output is correct
3 Correct 7 ms 712 KB Output is correct
4 Correct 8 ms 784 KB Output is correct
5 Correct 7 ms 784 KB Output is correct
6 Execution timed out 3018 ms 2136 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 376 KB Output is correct
2 Correct 8 ms 604 KB Output is correct
3 Correct 7 ms 712 KB Output is correct
4 Correct 8 ms 784 KB Output is correct
5 Correct 7 ms 784 KB Output is correct
6 Execution timed out 3018 ms 2136 KB Time limit exceeded
7 Halted 0 ms 0 KB -