oj.uz

Submission #61504

# Submission time Handle Problem Language Result Execution time Memory
61504 2018-07-26T06:02:26 Z 윤교준(#1780) Election (BOI18_election) C++11
0 / 100
 30 ms 24056 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);
					V.pop_back();
					bit.upd(i, -1);
				}
			} 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
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 30 ms 24056 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 54.0

# Verdict Execution time Memory Grader output
1 Incorrect 30 ms 24056 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 30 ms 24056 KB Output isn't correct
2 Halted 0 ms 0 KB -