oj.uz

Submission #386837

# Submission time Handle Problem Language Result Execution time Memory
386837 2021-04-07T13:02:28 Z Return_0 Election (BOI18_election) C++17
100 / 100
 1156 ms 83816 KB 
#pragma GCC optimize("Ofast,unroll-loops")
// #pragma comment(linker, "/stack:200000000")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma,tune=native")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef int ll;
typedef long double ld;
typedef pair <ll, ll> pll;

#ifdef SINA
#define dbg(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1> void __f(const char* name, Arg1&& arg1) { cout << name << " : " << arg1 << std::endl; }
template <typename Arg1, typename... Args> void __f (const char* names, Arg1&& arg1, Args&&... args) {
	const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...); }
#define dbg2(x, j, n) cout<< #x << " : "; output((j), (n), x, 1); cout.flush();
#else
#define dbg(...) 0
#define dbg2(x, j, n) 0
#endif
#define SZ(x) ((ll)((x).size()))
#define File(s, t) freopen(s ".txt", "r", stdin); freopen(t ".txt", "w", stdout);
#define input(j, n, a) for (int _i = (j); _i < (n)+(j); _i++) cin>> a[_i];
#define output(j, n, a, t) for (int _i = (j); _i < (n)+(j); _i++) cout<< a[_i] << (((t) && _i != (n)+(j)-1)? ' ' : '\n');
#define kill(x) return cout<< (x) << endl, 0
#define cl const ll
#define fr first
#define sc second
#define lc (v << 1)
#define rc (lc | 1)
#define mid ((l + r) >> 1)
#define All(x) (x).begin(), (x).end()

cl inf = sizeof(ll) == 4 ? (1e9 + 10) : (3e18), mod = 1e9 + 7, MOD = 998244353;

template <class A,class B> ostream& operator << (ostream& out,const pair<A,B>&a){return out<<'('<<a.first<<", "<<a.second<<')';}
template <class A> ostream& operator << (ostream& out, const vector<A> &a) {
	out<< '['; for (int i = -1; ++i < int(a.size());) out<< a[i] << (i + 1 < int(a.size()) ? ", " : ""); return out<<']'; }
template <class T, typename _t = less <T> > using Tree = tree <T, null_type, _t, rb_tree_tag, tree_order_statistics_node_update>;

cl N = 5e5 + 7;

struct segtree {
	ll l, r, mn, lz;
	segtree *lt, *rt;
	inline segtree (cl &L = 1, cl &R = N - 2) : l(L), r(R), mn(0), lz(0) {}

	void build () {
		if (l == r) return;
		lt = new segtree (l, mid);
		rt = new segtree (mid + 1, r);
		lt->build();
		rt->build();
	}

	inline void push (cl &x) { mn += x; lz += x; }
	inline void shift () { if (lz) { lt->push(lz); rt->push(lz); lz = 0; } }

	void upd (cl &ql, cl &qr, cl &x) {
		if (r < ql || qr < l)   return;
		if (ql <= l && r <= qr) { push(x); return; }
		shift();
		lt->upd(ql, qr, x);
		rt->upd(ql, qr, x);
		mn = min(lt->mn, rt->mn);
	}

	ll ask (cl &ql, cl &qr) {
		if (r < ql || qr < l)   return inf;
		if (ql <= l && r <= qr) return mn;
		shift();
		return min(lt->ask(ql, qr), rt->ask(ql, qr));
	}

} seg;

ll a [N], ans [N], n, q;
vector <pll> ql [N];
vector <ll> neg; ll Count (cl &x) { return neg.end() - lower_bound(All(neg), x); }
ll _get (cl &pos) { return (!pos ? 0 : seg.ask(pos, pos)); }

int main ()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	cin>> n;
	for (ll i = 1; i <= n; i++) {
		char c; cin>> c;
		a[i] = (c == 'T' ? -1 : 1);
	}
	cin>> q;
	for (ll i = 1, l, r; i <= q; i++) {
		cin>> l >> r;
		ql[r].push_back({l, i});
	}

	seg.r = n; seg.build();
	for (ll i = 1; i <= n; i++) {
		if (a[i] == 1) {
			seg.upd(i, n, 1);
			if (!neg.empty()) seg.upd(neg.back(), n, -1), neg.pop_back();
		}
		else neg.push_back(i);
		for (auto [l, id] : ql[i]) ans[id] = Count(l) - min(0, seg.ask(l, i) - _get(l - 1));
	}

	output(1, q, ans, 0);

	cerr<< "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";

	return 0;
}
/*

*/

Subtask #1
28.0 / 28.0

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

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12396 KB Output is correct
2 Correct 11 ms 12396 KB Output is correct
3 Correct 12 ms 12396 KB Output is correct
4 Correct 12 ms 12396 KB Output is correct
5 Correct 12 ms 12396 KB Output is correct
6 Correct 117 ms 21740 KB Output is correct
7 Correct 101 ms 21356 KB Output is correct
8 Correct 97 ms 21484 KB Output is correct
9 Correct 105 ms 21740 KB Output is correct
10 Correct 114 ms 21740 KB Output is correct
11 Correct 141 ms 21996 KB Output is correct
12 Correct 114 ms 21868 KB Output is correct
13 Correct 114 ms 22116 KB Output is correct
14 Correct 114 ms 21868 KB Output is correct
15 Correct 128 ms 21740 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12396 KB Output is correct
2 Correct 11 ms 12396 KB Output is correct
3 Correct 12 ms 12396 KB Output is correct
4 Correct 12 ms 12396 KB Output is correct
5 Correct 12 ms 12396 KB Output is correct
6 Correct 117 ms 21740 KB Output is correct
7 Correct 101 ms 21356 KB Output is correct
8 Correct 97 ms 21484 KB Output is correct
9 Correct 105 ms 21740 KB Output is correct
10 Correct 114 ms 21740 KB Output is correct
11 Correct 141 ms 21996 KB Output is correct
12 Correct 114 ms 21868 KB Output is correct
13 Correct 114 ms 22116 KB Output is correct
14 Correct 114 ms 21868 KB Output is correct
15 Correct 128 ms 21740 KB Output is correct
16 Correct 1147 ms 82156 KB Output is correct
17 Correct 902 ms 78656 KB Output is correct
18 Correct 952 ms 80492 KB Output is correct
19 Correct 883 ms 81956 KB Output is correct
20 Correct 1090 ms 81132 KB Output is correct
21 Correct 1156 ms 83560 KB Output is correct
22 Correct 1109 ms 83180 KB Output is correct
23 Correct 1121 ms 83816 KB Output is correct
24 Correct 1099 ms 83180 KB Output is correct
25 Correct 1146 ms 82412 KB Output is correct