oj.uz

답안 #310451

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
310451 2020-10-07T02:20:57 Z arwaeystoamneg Election (BOI18_election) C++17
100 / 100
 736 ms 70536 KB 
/*
ID: awesome35
LANG: C++14
TASK: milk4
*/
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#include<unordered_set>
#include<unordered_map>
#include<chrono>

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pair<int, int>> vpi;
typedef vector<pair<ll, ll>> vpll;

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

#define pb push_back
#define mp make_pair
#define rsz resize
#define sz(x) int(x.size())
#define all(x) x.begin(),x.end()
#define f first
#define s second
#define cont continue
#define endl '\n'
#define ednl '\n'
#define test int testc;cin>>testc;while(testc--)
#define pq priority_queue
const int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 }; // for every grid problem!!
const ll linf = 4000000000000000000LL;
const ll inf = 1000000007;//998244353
const ld pi = 3.1415926535;

void pv(vi a) { trav(x, a)cout << x << " "; cout << endl; }void pv(vll a) { trav(x, a)cout << x << " "; cout << endl; }void pv(vector<vi>a) {
	F0R(i, a.size()) { cout << i << endl; pv(a[i]); cout << endl; }
}void pv(vector<vll>a) { F0R(i, a.size()) { cout << i << endl; pv(a[i]); }cout << endl; }void pv(vector<string>a) { trav(x, a)cout << x << endl; cout << endl; }
void build_primes(vi& primes, int size)
{
	vi visited;
	visited.rsz(size, 0);
	FOR(i, 2, size)
	{
		if (visited[i] == 0)
		{
			primes.pb(i);
			int a = i;
			while (a < size)
			{
				visited[a] = 1;
				a += i;
			}
		}
	}
}
vector<vector<ll>> matrix_mult(vector<vector<ll>>& a, vector<vector<ll>>& b)
{
	int n = a.size();
	vector<vector<ll>> answer;
	answer.resize(n);
	for (int i = 0; i < n; i++) answer[i].resize(n, 0);
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++) // calculate answer[i][j]
		{
			for (int k = 0; k < n; k++)
				answer[i][j] = (answer[i][j] + a[i][k] * b[k][j]) % inf;
		}
	}
	return answer;
}
int modInverse(int a, int m)
{
	int m0 = m;
	int y = 0, x = 1;
	if (m == 1)
		return 0;
	while (a > 1)
	{
		// q is quotient 
		int q = a / m;
		int t = m;
		// m is remainder now, process same as 
		// Euclid's algo 
		m = a % m, a = t;
		t = y;
		// Update y and x 
		y = x - q * y;
		x = t;
	}
	// Make x positive 
	if (x < 0)
		x += m0;

	return x;
}
ll power(ll x, ll y)
{
	ll k = 1 << 30;
	ll z = 1;
	while (k != 0)
	{
		z *= z;
		z %= inf;
		if (y >= k)
		{
			z *= x;
			z %= inf;
			y -= k;
		}
		k >>= 1;
	}
	return z;
}
struct point
{
	ld x, y;
};
struct pt
{
	ll x, y;
};
// remember that you need to take abs
long double area(point x, point y, point z)
{
	return (x.y * y.x + y.y * z.x + z.y * x.x - x.x * y.y - y.x * z.y - z.x * x.y) / 2.0;
}
bool clockwise(point x, point y, point z)
{
	return area(x, y, z) > 0;
}
// remember that you need to take abs
long double area(pt x, pt y, pt z)
{
	return (x.y * y.x + y.y * z.x + z.y * x.x - x.x * y.y - y.x * z.y - z.x * x.y) / 2.0;
}
bool clockwise(pt x, pt y, pt z)
{
	return area(x, y, z) > 0;
}
int gcd(int a, int b)
{
	if (a > b)swap(a, b);
	if (a == 0)return b;
	return gcd(a, b % a);
}
int popcount(int a)
{
	int count = 0;
	while (a != 0)
	{
		count += (a % 2);
		a >>= 1;
	}
	return count;
}
ll choose(ll n, ll r)
{
	ll p = 1, k = 1;
	if (n - r < r)
		r = n - r;
	if (r != 0) {
		while (r) {
			p *= n;
			k *= r;
			long long m = gcd(p, k);
			p /= m;
			k /= m;
			n--;
			r--;
		}
	}
	else
		p = 1;
	return p;
}
vll prefix_hash(string& a, vll& powers)
{
	int n = sz(a);
	vll prefix(n + 1);
	F0R(i, n)prefix[i + 1] = (prefix[i] + powers[i] * (a[i] - 'a' + 1)) % inf;
	return prefix;
}
struct custom_hash {
	static uint64_t splitmix64(uint64_t x) {
		// http://xorshift.di.unimi.it/splitmix64.c
		x += 0x9e3779b97f4a7c15;
		x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
		x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
		return x ^ (x >> 31);
	}
	size_t operator()(uint64_t x) const {
		static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
		return splitmix64(x + FIXED_RANDOM);
	}
};
struct custom_hash_fast {
	size_t operator()(uint64_t x) const {
		static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
		x ^= FIXED_RANDOM;
		return x ^ (x >> 16);
	}
}; 
class segment_tree
{
	struct item
	{
		ll sum, prefix, suffix, ans;
	};
	item single(ll i)
	{
		if (i == 1)
			return { i,1,1 };
		return { i,0,0 };
	}
	item merge(item x, item y)
	{
		item ans = { 0,0,0,0 };
		ans.sum = x.sum + y.sum;
		ans.prefix = max(x.prefix, y.prefix + x.sum);
		ans.suffix = max(y.suffix, x.suffix + y.sum);
		ans.ans = max({ x.ans + y.sum,x.sum + y.ans,x.prefix + y.suffix });
		return ans;
	}
	vector<item> tree;
	vector<item>A;
	int height;
	item neutral = { 0,0,0,0 };
public:void build(vll& B)
{
	int	n = B.size();
	height = log2(n - 1) + 1;
	A.rsz(n);
	tree.rsz((1 << height + 1) - 1);
	F0R(i, n)A[i] = single(B[i]);
	A.rsz(1 << height, neutral);
	build(A, 0, 0, (1 << height) - 1);
}
	   void build(vector<item>& A, int v, int tl, int tr)
	   {
		   if (tl == tr)
			   tree[v] = A[tl];
		   else
		   {
			   int mid = (tl + tr) / 2;
			   build(A, 2 * v + 1, tl, mid);
			   build(A, 2 * v + 2, mid + 1, tr);
			   tree[v] = merge(tree[2 * v + 1], tree[2 * v + 2]);
		   }
	   }
public:ll query(int l, int r)
{
	item ans = query(0, 0, (1 << height) - 1, l, r);
	return ans.ans;
}
	   item query(int v, int tl, int tr, int l, int r)
	   {
		   if (r<tl || l>tr)return neutral;
		   if (l <= tl && r >= tr)
		   {
			   return tree[v];
		   }
		   int mid = (tl + tr) / 2;
		   return merge(query(2 * v + 1, tl, mid, l, r), query(2 * v + 2, mid + 1, tr, l, r));
	   }
	   //assign
public:void update(int pos, int val)
{
	update(0, 0, (1 << height) - 1, pos, single(val));
}
	   void update(int v, int tl, int tr, int pos, item val)
	   {
		   if (tl == tr)
		   {
			   tree[v] = val;
		   }
		   else
		   {
			   int mid = (tl + tr) / 2;
			   if (pos <= mid)
				   update(2 * v + 1, tl, mid, pos, val);
			   else
				   update(2 * v + 2, mid + 1, tr, pos, val);
			   tree[v] = merge(tree[2 * v + 1], tree[2 * v + 2]);
		   }
	   }
};

void setIO(string s) {
	ios_base::sync_with_stdio(0); cin.tie(0);
	//freopen((s + ".in").c_str(), "r", stdin);
	//freopen((s + ".out").c_str(), "w", stdout);
}
int main()
{
	setIO("test1");
	int n;
	string a;
	cin >> n >> a;
	vll t(n);
	F0R(i, n)t[i] = (a[i] == 'C' ? -1 : 1);
	segment_tree m;
	m.build(t);
	test
	{
		int l,r; cin >> l >> r;
	cout << m.query(l - 1, r - 1) << endl;
	}
}

Compilation message

election.cpp: In function 'void pv(std::vector<std::vector<int> >)':
election.cpp:22:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 | #define FOR(i,a,b) for (int i = (a); i < (b); ++i)
      |                                        ^
election.cpp:23:18: note: in expansion of macro 'FOR'
   23 | #define F0R(i,a) FOR(i,0,a)
      |                  ^~~
election.cpp:46:2: note: in expansion of macro 'F0R'
   46 |  F0R(i, a.size()) { cout << i << endl; pv(a[i]); cout << endl; }
      |  ^~~
election.cpp: In function 'void pv(std::vector<std::vector<long long int> >)':
election.cpp:22:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 | #define FOR(i,a,b) for (int i = (a); i < (b); ++i)
      |                                        ^
election.cpp:23:18: note: in expansion of macro 'FOR'
   23 | #define F0R(i,a) FOR(i,0,a)
      |                  ^~~
election.cpp:47:26: note: in expansion of macro 'F0R'
   47 | }void pv(vector<vll>a) { F0R(i, a.size()) { cout << i << endl; pv(a[i]); }cout << endl; }void pv(vector<string>a) { trav(x, a)cout << x << endl; cout << endl; }
      |                          ^~~
election.cpp: In member function 'void segment_tree::build(vll&)':
election.cpp:244:24: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
  244 |  tree.rsz((1 << height + 1) - 1);
      |                 ~~~~~~~^~~

Subtask #1
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 640 KB Output is correct
2 Correct 2 ms 640 KB Output is correct
3 Correct 2 ms 640 KB Output is correct
4 Correct 2 ms 640 KB Output is correct
5 Correct 2 ms 640 KB Output is correct

Subtask #2
54.0 / 54.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 640 KB Output is correct
2 Correct 2 ms 640 KB Output is correct
3 Correct 2 ms 640 KB Output is correct
4 Correct 2 ms 640 KB Output is correct
5 Correct 2 ms 640 KB Output is correct
6 Correct 81 ms 15872 KB Output is correct
7 Correct 72 ms 15872 KB Output is correct
8 Correct 79 ms 15872 KB Output is correct
9 Correct 76 ms 15872 KB Output is correct
10 Correct 84 ms 15872 KB Output is correct
11 Correct 81 ms 15872 KB Output is correct
12 Correct 81 ms 15872 KB Output is correct
13 Correct 83 ms 15872 KB Output is correct
14 Correct 84 ms 15788 KB Output is correct
15 Correct 84 ms 15872 KB Output is correct

Subtask #3
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 640 KB Output is correct
2 Correct 2 ms 640 KB Output is correct
3 Correct 2 ms 640 KB Output is correct
4 Correct 2 ms 640 KB Output is correct
5 Correct 2 ms 640 KB Output is correct
6 Correct 81 ms 15872 KB Output is correct
7 Correct 72 ms 15872 KB Output is correct
8 Correct 79 ms 15872 KB Output is correct
9 Correct 76 ms 15872 KB Output is correct
10 Correct 84 ms 15872 KB Output is correct
11 Correct 81 ms 15872 KB Output is correct
12 Correct 81 ms 15872 KB Output is correct
13 Correct 83 ms 15872 KB Output is correct
14 Correct 84 ms 15788 KB Output is correct
15 Correct 84 ms 15872 KB Output is correct
16 Correct 727 ms 70392 KB Output is correct
17 Correct 612 ms 70536 KB Output is correct
18 Correct 706 ms 70412 KB Output is correct
19 Correct 586 ms 70412 KB Output is correct
20 Correct 729 ms 70412 KB Output is correct
21 Correct 736 ms 70412 KB Output is correct
22 Correct 732 ms 70412 KB Output is correct
23 Correct 736 ms 70412 KB Output is correct
24 Correct 730 ms 70408 KB Output is correct
25 Correct 728 ms 70412 KB Output is correct