제출 #688911

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

street_lamps

#include <bits/stdc++.h>

using namespace std;

struct BIT{

	int qry(int x, int y){
		return 0;
	}
} bit;

struct segment{
	int l, r, t;
	bool operator< (const segment& o) const {
		return l < o.l || l == o.l && r < o.r;
	}
	void add(int t2) const {
		// cout << "ADD " << l << ' ' << r << ' ' << t << ' ' << t2 << endl;
	}
};

set<segment> S;
bool on[300002];

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; 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; ptr->add(t); S.erase(ptr); }
		if(on[x + 1]) { auto ptr = S.lower_bound({x, -1}); r = ptr->r; ptr->add(t); S.erase(ptr); }
		S.insert({l, r, t});
	}
	on[x] = !on[x];
	// show();
}

int query(int l, int r, int t){
	// cout << "QUERY " << l << ' ' << r << ' ' << t << endl;
	int ans = bit.qry(r, r) - bit.qry(l, r) - bit.qry(l, l) + bit.qry(r, r);
	auto ptr = S.lower_bound({l, 1 << 30}); 
	if(ptr != S.begin() && prev(ptr)->l <= l && r <= prev(ptr)->r) ans += t - prev(ptr)->t;
	return ans;
}

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); show();
	for(int t = 1; t <= q; t++){
		string type; cin >> type;
		if(type == "query"){
			int l, r; cin >> l >> r;
			cout << query(l, r, t) << endl;
		}else{
			int x; cin >> x; toggle(x, t);
		}
	}
}

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

street_lamps.cpp: In member function 'bool segment::operator<(const segment&) const':
street_lamps.cpp:15:30: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   15 |   return l < o.l || l == o.l && r < o.r;
      |                     ~~~~~~~~~^~~~~~~~~~
street_lamps.cpp: In function 'void show()':
street_lamps.cpp:26:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   26 |  for(auto i : S) cout << '[' << i.l << ", " << i.r << ']' << ' '; cout << '\n';
      |  ^~~
street_lamps.cpp:26:67: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   26 |  for(auto i : S) cout << '[' << i.l << ", " << i.r << ']' << ' '; cout << '\n';
      |                                                                   ^~~~
street_lamps.cpp: In function 'int32_t main()':
street_lamps.cpp:62:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   62 |  for(auto s : v) S.insert(s); show();
      |  ^~~
street_lamps.cpp:62:31: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   62 |  for(auto s : v) S.insert(s); show();
      |                               ^~~~

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