Submission #125095

#	Time	Username	Problem	Language	Result	Execution time	Memory
125095		Just_Solve_The_Problem	Street Lamps (APIO19_street_lamps)	C++11	0 / 100	20 ms	14840 KiB

street_lamps

#include <bits/stdc++.h>
 
#define ll long long
 
using namespace std;
 
const int N = (int)3e5 + 7;

int n, q;

struct fen {
	ll tree[N];
	fen() {
		memset(tree, 0, sizeof tree);
	}
	void upd(int pos, int val) {
		while (pos <= n) {
			tree[pos] += val;
			pos |= (pos + 1);
		}
	}
	ll get(int r) {
		ll res = 0;
		while (r >= 0) {
			res += tree[r];
			r = (r & (r + 1)) - 1;
		}
		return res;
	}
	ll get(int l, int r) {
		return get(r) - get(l - 1);
	}
};
fen pr;

struct T {
	int tree[N * 4];
	T() {
		memset(tree, 0, sizeof tree);
	}
	void upd(int pos, int val, int v = 1, int tl = 0, int tr = n - 1) {
		if (tl == tr) {
			tree[v] = val;
			return ;
		}
		int mid = (tl + tr) >> 1;
		if (pos <= mid)
			upd(pos, val, v + v, tl, mid);
		else
			upd(pos, val, v + v + 1, mid + 1, tr);
		tree[v] = max(tree[v + v], tree[v + v + 1]);
	}
	int get(int l, int r, int v = 1, int tl = 0, int tr = n - 1) {
		if (tl > r || tr < l) return -1;
		if (l <= tl && tr <= r) return tree[v];
		int mid = (tl + tr) >> 1;
		return max(get(l, r, v + v, tl, mid), get(l, r, v + v + 1, mid + 1, tr));
	}
};
T tr;

string s;
int cnt[N];
int lst[N];
int ans[N], tp[N];

pair<int, int> get(int s) {
	int S = s;
	for (int i = 18; i >= 0; i--) {
		if (pr.get(max(s - (1 << i), 1), s) == s - max(s - (1 << i), 1) + 1) {
			s = max(s - (1 << i), 1);
		}
	}
	int Left = s;
	s = S;
	for (int i = 18; i >= 0; i--) {
		if (pr.get(s, min(s + (1 << i), n)) == min(s + (1 << i), n) - s + 1) {
			s = min(s + (1 << i), n);
		}
	}
	int Right = s;
	return {Left, Right};
}

main() {
	scanf("%d %d", &n, &q);
	cin >> s;
	for (int i = 0; i < n; i++) {
		if (s[i] == '1') {
			lst[i] = -1;
			pr.upd(i, 1);
		}
		tr.upd(i, lst[i]);
	}
	for (int i = 1; i <= q; i++) {
		string tp;
		cin >> tp;
		if (tp[0] == 't') {
			int ind;
			scanf("%d", &ind); ind--;
			s[ind] ^= 1;
			if (s[ind] == '1') {
				lst[ind] = i - 1;
				tr.upd(ind, lst[ind]);
				pr.upd(ind, 1);
			} else {
				pair<int, int> ar = get(ind);
				pr.upd(ind, -1);
				// ******
			}
		} else {
			tp[i] = 1;
			int a, b;
			scanf("%d %d", &a, &b); a--; b--;
			if (pr.get(a, b - 1) == b - a) {
				ans[i] += (i - tr.get(a, b - 1) - 1);
			}
		}
	}
	
}
/*
5 7
11011
query 1 2
query 1 2
query 1 6
query 3 4
toggle 3
query 3 4
query 1 6
*/

Compilation message (stderr)

street_lamps.cpp:85:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:107:20: warning: variable 'ar' set but not used [-Wunused-but-set-variable]
     pair<int, int> ar = get(ind);
                    ^~
street_lamps.cpp:86:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &q);
  ~~~~~^~~~~~~~~~~~~~~~~
street_lamps.cpp:100:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &ind); ind--;
    ~~~~~^~~~~~~~~~~~
street_lamps.cpp:114:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d", &a, &b); a--; b--;
    ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 20
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20