oj.uz

Submission #712674

# Submission time Handle Problem Language Result Execution time Memory
712674 2023-03-19T12:53:41 Z MISM06 Street Lamps (APIO19_street_lamps) C++17
100 / 100
 2698 ms 270400 KB 
//0 1 1 0 1
//0 1 0 0 1
//1 0 0 1 1
//0 1 1 0 1
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2")

using namespace std;

#define F 			first
#define S 			second
#define pb 			push_back
#define sze			size()
#define	all(x)		x.begin() , x.end()
#define wall__		cout << "--------------------------------------\n";
#define kid 		int mid = (tl + tr) >> 1, cl = v << 1, cr = v << 1 | 1
#define file_io		freopen("input.cpp", "r", stdin); freopen("output.cpp", "w", stdout);

typedef long long ll;
typedef long double dl;
typedef pair < int , int > pii;
typedef pair < int , ll > pil;
typedef pair < ll , int > pli;
typedef pair < ll , ll > pll;
typedef pair < int , pii > piii;
typedef pair < ll, pll > plll;
typedef pair < pii , pii > piiii;


const ll N = 3e5 + 10;
const ll mod = 1e9 + 7;
const ll inf = 2e16;
const ll rinf = -2e16;
const ll INF = 1e9 + 10;
const ll rINF = -1e9 - 10;
const ll lg = 32;

// phase one :
int n, q, a[N], ans[N]; //number of lamps, number of queries, situation of lamps, answer of query i;
set < piii > st; //blocks of equal lamps in type : {l, {r, situation}};
vector < piii > qu[N]; //queries in type of : {0, {idx, 0}} = {toggle of a[idx]} , {1, {l, r}} = {ask about segment [l, r]};
vector < piiii > timeline[N]; // orders of type : {{0, val} , {l, r}} = {{its ask, value that should plus anwer}, {segment of asking}}
								//, {{1, val}, {l, r}} = plus val to segments of segment [l, r];
vector < int > sgs[N]; //segments of asking in type : sgs[l] {r1, r2, ...};

piii find_block (int idx) {
	if (idx < 1 || idx > n) return {-1, {-1, -1}};
	auto it = st.lower_bound({idx + 1, {0, 0}});
	it = prev(it);
	return *it;
} //find block of idx;

// phase two : 

struct node {
	vector < int > Bit;
	vector < pii > Rs;
	int L, R, sz;
	void make (int l, int r) {
		L = l; R = r; 
		Bit.pb(rINF);
		Rs.pb({-1, -1});
		for (int i = l; i <= r; i++) 
			for (auto x : sgs[i]) 
				Rs.pb({x, i});
		sort(all(Rs));
		sz = Rs.sze; --sz;
		for (int i = 1; i <= sz; i++) Bit.pb(0);
	}
	int get_range (int idx) {
		auto it = lower_bound(all(Rs), make_pair(idx + 1, 0));
		if (it == Rs.end()) return sz;
		int res = it - Rs.begin();
		--res; return res;
	}
	int get_id (int l, int r) {
		return lower_bound(all(Rs), make_pair(r, l)) - Rs.begin();
	}
	void point (int val, int idx) {
		for (; idx <= sz; idx += (idx & -idx)) Bit[idx] += val;
	}
	void range (int val, int l, int r) {
		point(val, l);
		if (r < sz) point(-val, r + 1);
	}
	int read (int idx) {
		int res = 0;
		for (; idx > 0; idx -= (idx & -idx))
			res += Bit[idx];
		return res;
	}
} seg[N << 2];

void build (int v = 1, int tl = 1, int tr = n) {
	seg[v].make(tl, tr);
	if (tl == tr) return;
	kid;
	build (cl, tl, mid);
	build (cr, mid + 1, tr);
}

void upd (int Lpos, int Rpos, int val, int v = 1, int tl = 1, int tr = n) {
	if (tl >= Lpos) {
		int idx = seg[v].get_range(Rpos);
		if (idx) seg[v].range(val, 1, idx);
		return;
	}
	kid;
	if (Lpos <= mid) upd (Lpos, Rpos, val, cl, tl, mid);
	upd (Lpos, Rpos, val, cr, mid + 1, tr);
}

int ask (int Lpos, int Rpos, int v = 1, int tl = 1, int tr = n) {
	int res = 0;
	if (tl <= Lpos && Lpos <= tr) {
		int idx = seg[v].get_id(Lpos, Rpos);
		res += seg[v].read(idx);
	} 
	if (tl == tr) return res;
	kid;
	if (Lpos <= mid) return res + ask(Lpos, Rpos, cl, tl, mid);
	else return res + ask(Lpos, Rpos, cr, mid + 1, tr);
}

void solve () {

	//phase one :
	cin >> n >> q;
	st.insert({1, {n, 0}});
	for (int i = 1; i <= n; i++) {
		char ch; cin >> ch;
		if (ch == '1') qu[0].pb({0, {i, 0}});
	} //input of lamps;
	for (int i = 1; i <= q; i++) {
		string ty; cin >> ty;
		if (ty == "query") {
			int l, r; cin >> l >> r;
			qu[i].pb({1, {l, r - 1}});
		} else {
			int idx; cin >> idx;
			qu[i].pb({0, {idx, 0}});
		}
	} //input queries;
	for (int i = 0; i <= q; i++) {
		for (auto query : qu[i]) {
			if (query.F == 1) {
				int l = query.S.F, r = query.S.S;
				auto bl = find_block(l), br = find_block(r);
				int val = 0;
				if (bl == br && bl.S.S == 1) val = -1 * (q - i);
				timeline[i].pb({{0, val}, {l, r}});
				sgs[l].pb(r);
			} else {
				int idx = query.S.F;
				auto bi =  find_block(idx);
				if (a[idx] == 1) {
					int L = bi.F, R = bi.S.F;
					timeline[i].pb({{1, -1 * (q - i)}, {L, R}});
					if (L < idx) timeline[i].pb({{1, q - i}, {L, idx - 1}});
					if (R > idx) timeline[i].pb({{1, q - i}, {idx + 1, R}});

					st.erase(bi);
					int l = idx, r = idx;
					if (L < idx) st.insert({L, {idx - 1, 1}});
					else if (L > 1) {
						auto bl = find_block(idx - 1);
						st.erase(bl);
						l = bl.F;
					}
					if (R > idx) st.insert({idx + 1, {R, 1}});
					else if (R < n) {
						auto br = find_block(idx + 1);
						st.erase(br);
						r = br.S.F;
					}
					st.insert({l, {r, 0}});
					a[idx] = 0;
				} else {
					int L = bi.F, R = bi.S.F;
					st.erase(bi);
					int l = idx, r = idx;
					if (L < idx) st.insert({L, {idx - 1, 0}});
					else if (L > 1) {
						auto bl = find_block(idx - 1);
						st.erase(bl);
						timeline[i].pb({{1, -1 * (q - i)}, {bl.F, bl.S.F}});
						l = bl.F;
					}
					if (R > idx) st.insert({idx + 1, {R, 0}});
					else if (R < n) {
						auto br = find_block(idx + 1);
						st.erase(br);
						timeline[i].pb({{1, -1 * (q - i)}, {br.F, br.S.F}});
						r = br.S.F;
					}	
					timeline[i].pb({{1, q - i}, {l, r}});
					st.insert({l, {r, 1}});
					a[idx] = 1;
				}
			}
		}
	} //make timeline;

	// phase two :
	build();
	for (int i = 0; i <= q; i++) {
		ans[i] = rINF;
		for (auto o : timeline[i]) {
			if (o.F.F == 0) {
				ans[i] = ask(o.S.F, o.S.S);
				ans[i] += o.F.S;
			} else upd(o.S.F, o.S.S, o.F.S);
		}
	}
	for (int i = 1; i <= q; i++) if (ans[i] != rINF) cout << ans[i] << '\n';
}


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

	int t = 1;
	// cin >> t;
	while (t--) {solve();}
    return 0;
}
/*
5 1
11011
query 1 2
*/
//inhonorofsbi;

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 96596 KB Output is correct
2 Correct 47 ms 96716 KB Output is correct
3 Correct 44 ms 96552 KB Output is correct
4 Correct 45 ms 96536 KB Output is correct
5 Correct 49 ms 96624 KB Output is correct
6 Correct 48 ms 96576 KB Output is correct
7 Correct 49 ms 96516 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 505 ms 141388 KB Output is correct
2 Correct 695 ms 145232 KB Output is correct
3 Correct 1000 ms 158976 KB Output is correct
4 Correct 1991 ms 224936 KB Output is correct
5 Correct 2065 ms 224320 KB Output is correct
6 Correct 1638 ms 209840 KB Output is correct
7 Correct 2127 ms 254128 KB Output is correct
8 Correct 2184 ms 270400 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 96832 KB Output is correct
2 Correct 46 ms 96836 KB Output is correct
3 Correct 49 ms 96880 KB Output is correct
4 Correct 57 ms 96908 KB Output is correct
5 Correct 983 ms 167308 KB Output is correct
6 Correct 1711 ms 195104 KB Output is correct
7 Correct 2233 ms 224528 KB Output is correct
8 Correct 2344 ms 263152 KB Output is correct
9 Correct 653 ms 142856 KB Output is correct
10 Correct 725 ms 147056 KB Output is correct
11 Correct 686 ms 148396 KB Output is correct
12 Correct 2213 ms 247416 KB Output is correct
13 Correct 2640 ms 263044 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 97028 KB Output is correct
2 Correct 50 ms 96984 KB Output is correct
3 Correct 46 ms 96828 KB Output is correct
4 Correct 45 ms 96844 KB Output is correct
5 Correct 2698 ms 261272 KB Output is correct
6 Correct 2115 ms 237816 KB Output is correct
7 Correct 1749 ms 212084 KB Output is correct
8 Correct 1114 ms 180840 KB Output is correct
9 Correct 574 ms 136336 KB Output is correct
10 Correct 363 ms 125792 KB Output is correct
11 Correct 589 ms 136340 KB Output is correct
12 Correct 362 ms 125984 KB Output is correct
13 Correct 634 ms 136336 KB Output is correct
14 Correct 360 ms 125772 KB Output is correct
15 Correct 2205 ms 246816 KB Output is correct
16 Correct 2292 ms 263192 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 96596 KB Output is correct
2 Correct 47 ms 96716 KB Output is correct
3 Correct 44 ms 96552 KB Output is correct
4 Correct 45 ms 96536 KB Output is correct
5 Correct 49 ms 96624 KB Output is correct
6 Correct 48 ms 96576 KB Output is correct
7 Correct 49 ms 96516 KB Output is correct
8 Correct 505 ms 141388 KB Output is correct
9 Correct 695 ms 145232 KB Output is correct
10 Correct 1000 ms 158976 KB Output is correct
11 Correct 1991 ms 224936 KB Output is correct
12 Correct 2065 ms 224320 KB Output is correct
13 Correct 1638 ms 209840 KB Output is correct
14 Correct 2127 ms 254128 KB Output is correct
15 Correct 2184 ms 270400 KB Output is correct
16 Correct 46 ms 96832 KB Output is correct
17 Correct 46 ms 96836 KB Output is correct
18 Correct 49 ms 96880 KB Output is correct
19 Correct 57 ms 96908 KB Output is correct
20 Correct 983 ms 167308 KB Output is correct
21 Correct 1711 ms 195104 KB Output is correct
22 Correct 2233 ms 224528 KB Output is correct
23 Correct 2344 ms 263152 KB Output is correct
24 Correct 653 ms 142856 KB Output is correct
25 Correct 725 ms 147056 KB Output is correct
26 Correct 686 ms 148396 KB Output is correct
27 Correct 2213 ms 247416 KB Output is correct
28 Correct 2640 ms 263044 KB Output is correct
29 Correct 47 ms 97028 KB Output is correct
30 Correct 50 ms 96984 KB Output is correct
31 Correct 46 ms 96828 KB Output is correct
32 Correct 45 ms 96844 KB Output is correct
33 Correct 2698 ms 261272 KB Output is correct
34 Correct 2115 ms 237816 KB Output is correct
35 Correct 1749 ms 212084 KB Output is correct
36 Correct 1114 ms 180840 KB Output is correct
37 Correct 574 ms 136336 KB Output is correct
38 Correct 363 ms 125792 KB Output is correct
39 Correct 589 ms 136340 KB Output is correct
40 Correct 362 ms 125984 KB Output is correct
41 Correct 634 ms 136336 KB Output is correct
42 Correct 360 ms 125772 KB Output is correct
43 Correct 2205 ms 246816 KB Output is correct
44 Correct 2292 ms 263192 KB Output is correct
45 Correct 263 ms 120628 KB Output is correct
46 Correct 460 ms 125480 KB Output is correct
47 Correct 992 ms 160036 KB Output is correct
48 Correct 1865 ms 220872 KB Output is correct
49 Correct 791 ms 153736 KB Output is correct
50 Correct 837 ms 153252 KB Output is correct
51 Correct 753 ms 155532 KB Output is correct
52 Correct 771 ms 165660 KB Output is correct
53 Correct 812 ms 165536 KB Output is correct
54 Correct 789 ms 165636 KB Output is correct