제출 #292093

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
292093		kajebiii	가로등 (APIO19_street_lamps)	C++17	20 / 100	545 ms	27992 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>;

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<ti> &dels, ti del, int q) {
	get<2>(del) = q - get<2>(del) + 1;
	dels.push_back(del);
}
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);
		}
	}

	vector<ti> dels;
	vector<ti> queries;
	for(int q=0; q<Q; q++) {
		char s[10]; scanf("%s", s);
		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];
			queries.emplace_back(a, b, q);
		}
	}
	sort(ALL(dels));
	sort(ALL(queries));
	int delsIx = 0;
	IDX idx = IDX(N+1);
	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, v; tie(x, y, v) = dels[delsIx++];
			idx.add(y, v);
		}

		int now = idx.getSum(b, N);
		//if(now != 0) printf(">> [%d] %d %d += %d\n", q, a, b, now);
		Ans[q] += now;
	}
	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) {
			//if(q-t+1 != 0) printf("<< [%d] %d %d += %d (%d)\n", q, a, b, q-t+1, t);
			Ans[q] += q - t + 1;
		}
	}

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

컴파일 시 표준 에러 (stderr) 메시지

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

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