Submission #292110

#	Time	Username	Problem	Language	Result	Execution time	Memory
292110		kajebiii	Street Lamps (APIO19_street_lamps)	C++17	100 / 100	1515 ms	174568 KiB

street_lamps

// Comment
//

#include <bits/stdc++.h>

using namespace std;

#define SZ(v) ((int)(v).size())
#define ALL(v) (v).begin(),(v).end()
#define one first
#define two second
using ll = long long;
using pi = pair<int, int>;
const int INF = 0x3f3f3f3f;
const ll LINF = 1ll * INF * INF;

using ti = tuple<int, int, int>;
using qi = tuple<int, int, int, int>;

const int MAX_N = 3e5 + 100;

struct IDX {
	int P; vector<int> val;
	IDX(int N) {
		for(P=1; P<N; P<<=1);
		val = vector<int>(2*P, 0);
	}
	void add(int v, int k) {
		val[v+=P] += k;
		while(v>>=1) val[v] = val[v*2] + val[v*2+1];
	}
	int getSum(int a, int b) {
		int res = 0;
		for(a+=P, b+=P; a<=b; a>>=1, b>>=1) {
			if(a%2==1) res += val[a++];
			if(b%2==0) res += val[b--];
		}
		return res;
	}
};

int N, Q;
int Nr[MAX_N];
set<ti> Lines;
vector<ti> Qs;
int Ans[MAX_N];

void addDel(vector<qi> &dels, ti del, int q) {
	int x, y, t; tie(x, y, t) = del;
	dels.push_back(qi(x, y, t, q));
}

vector<qi> Dels[MAX_N * 4];
IDX idx = IDX(1);
void dc(int ql, int qr, int ix) {
	int qm = (ql + qr) >> 1;

	vector<qi> &dels = Dels[ix];
	if(ql != qr) {
		dc(ql, qm, ix * 2);
		for(qi tt: Dels[ix*2  ]) Dels[ix].push_back(tt);
		
		sort(ALL(dels));
		// merge sort ?
		
		vector<ti> queries;
		for(int q=qm+1; q<=qr; q++) {
			if(get<0>(Qs[q]) == 1) {
				int a, b; tie(ignore, a, b) = Qs[q];
				queries.emplace_back(a, b, q);
			}
		}
		sort(ALL(queries));

		int delsIx = 0;
		for(ti query: queries) {
			int a, b, q; tie(a, b, q) = query;
			while(delsIx < SZ(dels) && get<0>(dels[delsIx]) <= a) {
				int x, y, ts, te; tie(x, y, ts, te) = dels[delsIx++];
				if(te >= ql) idx.add(y, te - max(ts, ql) + 1);
			}

			int now = idx.getSum(b, N);
			Ans[q] += now;
		}
		for(int i=0; i<delsIx; i++) {
			int x, y, ts, te; tie(x, y, ts, te) = dels[i];
			if(te >= ql) idx.add(y, -(te - max(ts, ql) + 1));
		}
		for(ti query: queries) {
			int a, b, q; tie(a, b, q) = query;
			if(SZ(Lines) == 0) continue;
			auto it = Lines.lower_bound(ti(a+1, -INF, -INF));
			it--;
			int x, y, t; tie(x, y, t) = *it;
			if(x <= a && b <= y) {
				Ans[q] += qm - max(ql, t) + 1;
			}
		}

		dc(qm+1, qr, ix*2+1);
		for(qi tt: Dels[ix*2+1]) Dels[ix].push_back(tt);
	}else{
		int q = ql;
		if(get<0>(Qs[q]) == 0) {
			int ix = get<1>(Qs[q]);
			if(Nr[ix] == 0) {
				int lv = Nr[ix-1], rv = Nr[ix+1];
				int l = ix, r = ix;
				auto it = Lines.begin();
				if(lv) {
					it = Lines.lower_bound(ti(ix, -INF, -INF));
					it--;
					l = get<0>(*it);
					Lines.erase(it);
					addDel(dels, *it, q);
				}
				if(rv) {
					it = Lines.lower_bound(ti(ix, -INF, -INF));
					r = get<1>(*it);
					Lines.erase(it);
					addDel(dels, *it, q);
				}
				Lines.emplace(ti(l, r, q+1));
			}else{
				auto it = Lines.lower_bound(ti(ix+1, -INF, -INF));
				it--;
				int l, r; tie(l, r, ignore) = *it;
				Lines.erase(it);
				addDel(dels, *it, q);

				if(l <= ix-1) Lines.emplace(ti(l, ix-1, q+1));
				if(r >= ix+1) Lines.emplace(ti(ix+1, r, q+1));
			}
			Nr[ix] = 1 - Nr[ix];
		}else{
			int a, b; tie(ignore, a, b) = Qs[q];
			if(SZ(Lines) == 0) return;
			auto it = Lines.lower_bound(ti(a+1, -INF, -INF));
			it--;
			int x, y, t; tie(x, y, t) = *it;
			if(x <= a && b <= y) {
				Ans[q] += 1;
			}
		}
	}
}
int main() {
	cin >> N >> Q;
	for(int i=1; i<=N; i++) scanf("%1d", &Nr[i]);
	for(int i=1; i<=N; i++) {
		if(Nr[i] == 0) continue;
		int st = i, en = i;
		while(en+1 <= N && Nr[en+1] == 1) en++;
		Lines.emplace(st, en, 0);
		i = en;
	}

	for(int q=0; q<Q; q++) {
		char s[10]; scanf("%s", s);
		if(s[0] == 't') {
			int ix; scanf("%d", &ix);
			Qs.emplace_back(0, ix, -1);
		}else{
			int a, b; scanf("%d%d", &a, &b);
			b = b-1;
			Qs.emplace_back(1, a, b);
		}
	}

	idx = IDX(N+1);
	dc(0, Q-1, 1);

	for(int q=0; q<Q; q++) {
		if(get<0>(Qs[q]) == 1) {
			printf("%d\n", Ans[q]);
		}
	}
	return 0;
}

Compilation message (stderr)

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:150:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  150 |  for(int i=1; i<=N; i++) scanf("%1d", &Nr[i]);
      |                          ~~~~~^~~~~~~~~~~~~~~
street_lamps.cpp:160:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  160 |   char s[10]; scanf("%s", s);
      |               ~~~~~^~~~~~~~~
street_lamps.cpp:162:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  162 |    int ix; scanf("%d", &ix);
      |            ~~~~~^~~~~~~~~~~
street_lamps.cpp:165:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  165 |    int a, b; scanf("%d%d", &a, &b);
      |              ~~~~~^~~~~~~~~~~~~~~~

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