oj.uz

Submission #61505

# Submission time Handle Problem Language Result Execution time Memory
61505 2018-07-26T06:03:26 Z 윤교준(#1780) Election (BOI18_election) C++11
100 / 100
 1170 ms 45308 KB 
#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define revv(V) reverse(allv(V))
#define sz(V) ((int)(V).size())
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define rb(x) ((x)&(-(x)))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, ll> pil;

const int MAXN = 500055;
const int MAXQ = 500055;

struct BIT {
	int d[MAXN];
	void upd(int x, int r) {
		for(x += 5; x < MAXN; x += rb(x))
			d[x] += r;
	}
	int get(int x) {
		int r = 0; for(x += 5; x; x -= rb(x))
			r += d[x];
		return r;
	}
} bit;

struct NOD {
	NOD(int sum = 0, int dt = 0)
		: sum(sum), dt(min(0, dt)) {}
	int sum, dt;

	NOD operator + (const NOD &t) const {
		return NOD(sum + t.sum, min(t.dt, t.sum + dt));
	}
};

struct SEG {
	NOD nod[MAXN*3];

	void upd(int i, int s, int e, int x, int r) {
		if(s == e) {
			nod[i] = NOD(r, r);
			return;
		}
		int m = (s+e) >> 1;
		if(x <= m) upd(i<<1, s, m, x, r);
		else upd(i<<1|1, m+1, e, x, r);
		nod[i] = nod[i<<1] + nod[i<<1|1];
	}
	void upd(int x, int r) { upd(1, 0, MAXN-1, x, r); }
	NOD get(int i, int s, int e, int p, int q) {
		if(p <= s && e <= q) return nod[i];
		int m = (s+e) >> 1;
		if(q <= m) return get(i<<1, s, m, p, q);
		if(m < p) return get(i<<1|1, m+1, e, p, q);
		return get(i<<1, s, m, p, q) + get(i<<1|1, m+1, e, p, q);
	}
	NOD get(int s, int e) { return get(1, 0, MAXN-1, s, e); }
} seg;

vector<int> QV[MAXN];

char A[MAXN];
int B[MAXQ], C[MAXQ];

int Ans[MAXQ];
int N, Q;

int main() {
	scanf("%d %s%d", &N, A+1, &Q);
	for(int i = 1; i <= Q; i++) {
		scanf("%d%d", &B[i], &C[i]);
		QV[B[i]].eb(i);
	}

	{
		vector<int> V;
		for(int i = N; i; i--) {
			if('C' == A[i]) {
				seg.upd(i, 1);
				if(!V.empty()) {
					seg.upd(V.back(), -1);
					bit.upd(V.back(), -1);
					V.pop_back();
				}
			} else {
				V.eb(i);
				bit.upd(i, 1);
			}

			for(int v : QV[i])
				Ans[v] = -seg.get(i, C[v]).dt + bit.get(C[v]);
		}
	}

	for(int i = 1; i <= Q; i++) printf("%d\n", Ans[i]);
	return 0;
}

Compilation message

election.cpp: In function 'int main()':
election.cpp:78:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %s%d", &N, A+1, &Q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
election.cpp:80:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &B[i], &C[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 23928 KB Output is correct
2 Correct 25 ms 24164 KB Output is correct
3 Correct 26 ms 24164 KB Output is correct
4 Correct 25 ms 24164 KB Output is correct
5 Correct 24 ms 24164 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 23928 KB Output is correct
2 Correct 25 ms 24164 KB Output is correct
3 Correct 26 ms 24164 KB Output is correct
4 Correct 25 ms 24164 KB Output is correct
5 Correct 24 ms 24164 KB Output is correct
6 Correct 117 ms 26804 KB Output is correct
7 Correct 93 ms 26804 KB Output is correct
8 Correct 130 ms 26804 KB Output is correct
9 Correct 114 ms 26804 KB Output is correct
10 Correct 126 ms 26804 KB Output is correct
11 Correct 116 ms 27280 KB Output is correct
12 Correct 120 ms 27280 KB Output is correct
13 Correct 114 ms 27280 KB Output is correct
14 Correct 119 ms 27280 KB Output is correct
15 Correct 138 ms 27280 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 23928 KB Output is correct
2 Correct 25 ms 24164 KB Output is correct
3 Correct 26 ms 24164 KB Output is correct
4 Correct 25 ms 24164 KB Output is correct
5 Correct 24 ms 24164 KB Output is correct
6 Correct 117 ms 26804 KB Output is correct
7 Correct 93 ms 26804 KB Output is correct
8 Correct 130 ms 26804 KB Output is correct
9 Correct 114 ms 26804 KB Output is correct
10 Correct 126 ms 26804 KB Output is correct
11 Correct 116 ms 27280 KB Output is correct
12 Correct 120 ms 27280 KB Output is correct
13 Correct 114 ms 27280 KB Output is correct
14 Correct 119 ms 27280 KB Output is correct
15 Correct 138 ms 27280 KB Output is correct
16 Correct 1029 ms 44328 KB Output is correct
17 Correct 865 ms 44328 KB Output is correct
18 Correct 858 ms 44328 KB Output is correct
19 Correct 893 ms 44328 KB Output is correct
20 Correct 1170 ms 44328 KB Output is correct
21 Correct 1062 ms 45308 KB Output is correct
22 Correct 1067 ms 45308 KB Output is correct
23 Correct 978 ms 45308 KB Output is correct
24 Correct 1012 ms 45308 KB Output is correct
25 Correct 1106 ms 45308 KB Output is correct