oj.uz

Submission #431087

# Submission time Handle Problem Language Result Execution time Memory
431087 2021-06-17T09:24:29 Z Return_0 Street Lamps (APIO19_street_lamps) C++17
100 / 100
 4639 ms 275976 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")

#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 = 3e5 + 7;

ll n, q;
set <ll> off;
gp_hash_table <ll, ll> fen [N];
string s;

inline void add (ll l, cl &r, cl &x) { for (; l; l -= l & -l) for (ll i = r; i; i -= i & -i) fen[l][i] += x; }
inline void add_to_rect (cl &a, cl &b, cl &c, cl &d, cl &x) {
	add(b, d, x); add(a - 1, d, -x); add(b, c - 1, -x); add(a - 1, c - 1, x);
}
inline ll ask_sum (ll l, cl &r) {
	ll ret = 0;
	for (; l < N; l += l & -l) for (ll i = r; i < N; i += i & -i) if (fen[l].find(i) != fen[l].end()) ret += fen[l][i];
	return ret;
}

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

	cin>> n >> q >> s;
	off.insert(0); off.insert(n + 1);
	for (ll i = 0; i < n; i++) if (s[i] == '0') off.insert(i + 1);

	for (ll i = 1; i <= q; i++) {
		string tp; cin>> tp;
		if (tp == "toggle") {
			ll x; cin>> x;
			ll l = *(--off.lower_bound(x)) + 1, r = *off.upper_bound(x);
			if (off.count(x)) {
				off.erase(x);
				add_to_rect(l, x, x + 1, r, -i);
			} else {
				off.insert(x);
				add_to_rect(l, x, x + 1, r, i);
			}
		} else {
			ll l, r; cin>> l >> r;
			cout<< ask_sum(l, r) + (off.lower_bound(l) == off.upper_bound(r - 1) ? i : 0) << '\n';
		}
	}

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

	return 0;
}
/*
5 7
11011
query 1 2
query 1 2
query 1 6
query 3 4
toggle 3
query 3 4
query 1 6

*/

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 63616 KB Output is correct
2 Correct 85 ms 63624 KB Output is correct
3 Correct 78 ms 63672 KB Output is correct
4 Correct 70 ms 63696 KB Output is correct
5 Correct 66 ms 63656 KB Output is correct
6 Correct 73 ms 63708 KB Output is correct
7 Correct 85 ms 63708 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 551 ms 64640 KB Output is correct
2 Correct 665 ms 64856 KB Output is correct
3 Correct 1774 ms 68116 KB Output is correct
4 Correct 3382 ms 196800 KB Output is correct
5 Correct 3201 ms 200940 KB Output is correct
6 Correct 3483 ms 202364 KB Output is correct
7 Correct 1290 ms 78796 KB Output is correct
8 Correct 783 ms 66052 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 64068 KB Output is correct
2 Correct 87 ms 64084 KB Output is correct
3 Correct 74 ms 63968 KB Output is correct
4 Correct 71 ms 63656 KB Output is correct
5 Correct 4639 ms 275976 KB Output is correct
6 Correct 4288 ms 233128 KB Output is correct
7 Correct 4140 ms 200288 KB Output is correct
8 Correct 867 ms 66088 KB Output is correct
9 Correct 572 ms 64544 KB Output is correct
10 Correct 648 ms 64516 KB Output is correct
11 Correct 582 ms 64724 KB Output is correct
12 Correct 1485 ms 78692 KB Output is correct
13 Correct 817 ms 66096 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 63656 KB Output is correct
2 Correct 74 ms 63940 KB Output is correct
3 Correct 86 ms 63884 KB Output is correct
4 Correct 76 ms 63952 KB Output is correct
5 Correct 1951 ms 79368 KB Output is correct
6 Correct 3187 ms 179296 KB Output is correct
7 Correct 3599 ms 201840 KB Output is correct
8 Correct 3898 ms 219800 KB Output is correct
9 Correct 552 ms 64196 KB Output is correct
10 Correct 295 ms 63728 KB Output is correct
11 Correct 510 ms 64228 KB Output is correct
12 Correct 353 ms 63792 KB Output is correct
13 Correct 503 ms 64224 KB Output is correct
14 Correct 303 ms 63800 KB Output is correct
15 Correct 1531 ms 78668 KB Output is correct
16 Correct 777 ms 66136 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 63616 KB Output is correct
2 Correct 85 ms 63624 KB Output is correct
3 Correct 78 ms 63672 KB Output is correct
4 Correct 70 ms 63696 KB Output is correct
5 Correct 66 ms 63656 KB Output is correct
6 Correct 73 ms 63708 KB Output is correct
7 Correct 85 ms 63708 KB Output is correct
8 Correct 551 ms 64640 KB Output is correct
9 Correct 665 ms 64856 KB Output is correct
10 Correct 1774 ms 68116 KB Output is correct
11 Correct 3382 ms 196800 KB Output is correct
12 Correct 3201 ms 200940 KB Output is correct
13 Correct 3483 ms 202364 KB Output is correct
14 Correct 1290 ms 78796 KB Output is correct
15 Correct 783 ms 66052 KB Output is correct
16 Correct 80 ms 64068 KB Output is correct
17 Correct 87 ms 64084 KB Output is correct
18 Correct 74 ms 63968 KB Output is correct
19 Correct 71 ms 63656 KB Output is correct
20 Correct 4639 ms 275976 KB Output is correct
21 Correct 4288 ms 233128 KB Output is correct
22 Correct 4140 ms 200288 KB Output is correct
23 Correct 867 ms 66088 KB Output is correct
24 Correct 572 ms 64544 KB Output is correct
25 Correct 648 ms 64516 KB Output is correct
26 Correct 582 ms 64724 KB Output is correct
27 Correct 1485 ms 78692 KB Output is correct
28 Correct 817 ms 66096 KB Output is correct
29 Correct 75 ms 63656 KB Output is correct
30 Correct 74 ms 63940 KB Output is correct
31 Correct 86 ms 63884 KB Output is correct
32 Correct 76 ms 63952 KB Output is correct
33 Correct 1951 ms 79368 KB Output is correct
34 Correct 3187 ms 179296 KB Output is correct
35 Correct 3599 ms 201840 KB Output is correct
36 Correct 3898 ms 219800 KB Output is correct
37 Correct 552 ms 64196 KB Output is correct
38 Correct 295 ms 63728 KB Output is correct
39 Correct 510 ms 64228 KB Output is correct
40 Correct 353 ms 63792 KB Output is correct
41 Correct 503 ms 64224 KB Output is correct
42 Correct 303 ms 63800 KB Output is correct
43 Correct 1531 ms 78668 KB Output is correct
44 Correct 777 ms 66136 KB Output is correct
45 Correct 329 ms 64332 KB Output is correct
46 Correct 407 ms 64024 KB Output is correct
47 Correct 1807 ms 111540 KB Output is correct
48 Correct 3408 ms 196224 KB Output is correct
49 Correct 667 ms 64348 KB Output is correct
50 Correct 702 ms 64352 KB Output is correct
51 Correct 645 ms 64372 KB Output is correct
52 Correct 591 ms 64236 KB Output is correct
53 Correct 608 ms 64356 KB Output is correct
54 Correct 584 ms 64324 KB Output is correct