Submission #673826

#	Time	Username	Problem	Language	Result	Execution time	Memory
673826		QwertyPi	Street Lamps (APIO19_street_lamps)	C++14	0 / 100	5064 ms	13608 KiB

street_lamps

#include <bits/stdc++.h>
#define pii pair<int, int>
#define fi first
#define se second
using namespace std;

struct upd{
	int l, r, fr, to;
};

struct line{
	int l, r, x;
};

namespace bit2d{
	vector<int> solve(vector<upd> U, vector<line> Q){
		vector<int> ans(Q.size());
		for(int i = 0; i < U.size(); i++){
			for(int j = 0; j < Q.size(); j++){
				if(U[i].l <= Q[j].l && Q[j].r <= U[i].r && U[i].fr <= Q[j].x)
					ans[j] += min(Q[j].x, U[i].to) - U[i].fr;
			}
		}
		return ans;
	}
};

namespace gen_upd{
	
	struct range{
		int l, r, t;
		bool operator< (const range& o) const {
			return l < o.l;
		}
	};
	set<range> s; vector<bool> u;
	vector<upd> U;
	void init(string _s){
		u.resize(_s.size());
		for(int i = 0; i < _s.size(); i++) u[i] = _s[i] - '0';
		int l = 0, r = 0;
		for(int i = 0; i < _s.size(); i++){
			if(_s[i] == '1'){
				r = i + 1;
			}else{
				s.insert({l, r, 0});
				l = i + 1;
			}
		}
		s.insert({l, _s.size(), 0});
	}
	void add(int t, int x){
		if(u[x]){
			auto ptr = s.lower_bound({x + 1, 0}); --ptr;
			U.push_back({ptr->l, ptr->r, ptr->t, t});
			int l = ptr->l, r = ptr->r;
			s.erase(ptr);
			s.insert({ptr->l, x, t});
			s.insert({x + 1, ptr->r, t});
		}else{
			int l = x, r = x + 1;
			auto ptr = s.lower_bound({x + 1, 0});
			if(ptr != s.end() && ptr->l == x + 1){
				U.push_back({ptr->l, ptr->r, ptr->t, t});
				r = ptr->r; s.erase(ptr);
			}
			ptr = s.upper_bound({x, 0});
			if(ptr != s.begin() && prev(ptr)->r == x){
				ptr--;
				U.push_back({ptr->l, ptr->r, ptr->t, t});
				l = ptr->l; s.erase(ptr);
			}
			s.insert({l, r, t});
		}
		u[x] = !u[x];
	}
	void final(int t){
		for(auto i : s){
			U.push_back({i.l, i.r, i.t, t});
		}
	}
};

int main(){
	int n, q; cin >> n >> q; string s; cin >> s; gen_upd::init(s);
	vector<upd> U; vector<line> Q;
	for(int t = 1; t <= q; t++){
		string ty; cin >> ty;
		if(ty == "toggle"){
			int x; cin >> x; x--; gen_upd::add(t, x);
		}else{
			int ql, qr; cin >> ql >> qr; ql--; qr--; Q.push_back({ql, qr, t});
		}
	}
	gen_upd::final(q); U = gen_upd::U; 
	vector<int> ans = bit2d::solve(U, Q);
	for(auto a : ans){
		cout << a << endl;
	}
	cout << endl;
}

Compilation message (stderr)

street_lamps.cpp: In function 'std::vector<int> bit2d::solve(std::vector<upd>, std::vector<line>)':
street_lamps.cpp:18:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<upd>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |   for(int i = 0; i < U.size(); i++){
      |                  ~~^~~~~~~~~~
street_lamps.cpp:19:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |    for(int j = 0; j < Q.size(); j++){
      |                   ~~^~~~~~~~~~
street_lamps.cpp: In function 'void gen_upd::init(std::string)':
street_lamps.cpp:40:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |   for(int i = 0; i < _s.size(); i++) u[i] = _s[i] - '0';
      |                  ~~^~~~~~~~~~~
street_lamps.cpp:42:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |   for(int i = 0; i < _s.size(); i++){
      |                  ~~^~~~~~~~~~~
street_lamps.cpp:50:23: warning: narrowing conversion of '_s.std::__cxx11::basic_string<char>::size()' from 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
   50 |   s.insert({l, _s.size(), 0});
      |                ~~~~~~~^~
street_lamps.cpp: In function 'void gen_upd::add(int, int)':
street_lamps.cpp:56:8: warning: unused variable 'l' [-Wunused-variable]
   56 |    int l = ptr->l, r = ptr->r;
      |        ^
street_lamps.cpp:56:20: warning: unused variable 'r' [-Wunused-variable]
   56 |    int l = ptr->l, r = ptr->r;
      |                    ^

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