제출 #689294

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
689294		QwertyPi	가로등 (APIO19_street_lamps)	C++14	100 / 100	1469 ms	75760 KiB

street_lamps

#include <bits/stdc++.h>

using namespace std;

struct BIT{
	vector<int> ip[300011], bit[300011];
	void init(){
		for(int i = 0; i < 300011; i++){
			ip[i].push_back(0); sort(ip[i].begin(), ip[i].end());
			ip[i].resize(unique(ip[i].begin(), ip[i].end()) - ip[i].begin());
			bit[i].resize(ip[i].size());
		}
	}
	void init_add(int x, int y){
		for(int i = x; i < 300011; i += i & -i){
			ip[i].push_back(y);
		}
	}
	void add(int x, int y, int v){
		for(int i = x; i < 300011; i += i & -i){
			int y2 = lower_bound(ip[i].begin(), ip[i].end(), y) - ip[i].begin();
			for(int j = y2; j < ip[i].size(); j += j & -j){
				bit[i][j] += v;
			}
		}
	}
	int qry(int x, int y){
		int ret = 0;
		for(int i = x; i; i -= i & -i){
			int y2 = upper_bound(ip[i].begin(), ip[i].end(), y) - ip[i].begin() - 1;
			for(int j = y2; j; j -= j & -j){
				ret += bit[i][j];
			}
		}
		return ret;
	}
} bit;

struct segment{
	int l, r, t;
	bool operator< (const segment& o) const {
		return l < o.l || l == o.l && r < o.r;
	}
};

vector<segment> segs[300011];

void add(const segment& s, int t2) {
	// cout << "ADD " << s.l << ' ' << s.r << ' ' << s.t << ' ' << t2 << endl;
	bit.init_add(s.l, s.r); segs[t2].push_back(s);
}

set<segment> S;
bool on[300011], isq[300011];
int L[300011], R[300011], rans[300011];

void show(){
	for(auto i : S) cout << '[' << i.l << ", " << i.r << ']' << ' '; cout << '\n';
}

void toggle(int x, int t){
	// cout << "TOGGLE " << x << ' ' << t << endl;
	if(on[x]){
		auto ptr = S.lower_bound({x, 1 << 30}); --ptr; int l = ptr->l, r = ptr->r; add(*ptr, t); S.erase(ptr);
		if(on[x - 1]) { S.insert({l, x, t}); }
		if(on[x + 1]) { S.insert({x + 1, r, t}); }
	}else{
		int l = x, r = x + 1;
		if(on[x - 1]) { auto ptr = S.lower_bound({x, -1}); --ptr; l = ptr->l; add(*ptr, t); S.erase(ptr); }
		if(on[x + 1]) { auto ptr = S.lower_bound({x, -1}); r = ptr->r; add(*ptr, t); S.erase(ptr); }
		S.insert({l, r, t});
	}
	on[x] = !on[x];
	// show();
}

void query(int l, int r, int t){
	isq[t] = true; L[t] = l, R[t] = r;
	auto ptr = S.lower_bound({l, 1 << 30}); 
	if(ptr != S.begin() && prev(ptr)->l <= l && r <= prev(ptr)->r) rans[t] += t - prev(ptr)->t;
}

void query2(int l, int r, int t){
	// cout << l << ' ' << r << ' ' << bit.qry(300010, r) << ' ' << bit.qry(l - 1, r) << endl;
	rans[t] += bit.qry(l, 300010) - bit.qry(l, r - 1);
}

int32_t main(){
	int n, q; cin >> n >> q;
	string s; cin >> s; for(int i = 1; i <= n; i++) on[i] = s[i - 1] == '1';
	vector<segment> v; 
	for(int i = 1; i <= n; i++) {
		if(on[i]){
			if(v.size() && v.back().r == i) v.back().r++; else v.push_back({i, i + 1, 0});
		}
	}
	for(auto s : v) S.insert(s);
	for(int t = 1; t <= q; t++){
		string type; cin >> type;
		if(type == "query"){
			int l, r; cin >> l >> r;
			query(l, r, t);
		}else{
			int x; cin >> x; toggle(x, t);
		}
	}
	bit.init();
	for(int t = 1; t <= q; t++){
		for(auto s : segs[t]){
			bit.add(s.l, s.r, t - s.t);
		}
		if(isq[t]){
			query2(L[t], R[t], t);
		}
	}
	for(int t = 1; t <= q; t++){
		if(isq[t]){
			cout << rans[t] << endl;
		}
	}
}

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

street_lamps.cpp: In member function 'void BIT::add(int, int, int)':
street_lamps.cpp:22:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |    for(int j = y2; j < ip[i].size(); j += j & -j){
      |                    ~~^~~~~~~~~~~~~~
street_lamps.cpp: In member function 'bool segment::operator<(const segment&) const':
street_lamps.cpp:42:30: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   42 |   return l < o.l || l == o.l && r < o.r;
      |                     ~~~~~~~~~^~~~~~~~~~
street_lamps.cpp: In function 'void show()':
street_lamps.cpp:58:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   58 |  for(auto i : S) cout << '[' << i.l << ", " << i.r << ']' << ' '; cout << '\n';
      |  ^~~
street_lamps.cpp:58:67: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   58 |  for(auto i : S) cout << '[' << i.l << ", " << i.r << ']' << ' '; cout << '\n';
      |                                                                   ^~~~

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