Submission #246300

#	Time	Username	Problem	Language	Result	Execution time	Memory
246300		user202729	Street Lamps (APIO19_street_lamps)	C++17	100 / 100	4418 ms	153180 KiB

street_lamps

//oj.uz/problem/view/APIO19_street_lamps
// :(
#ifndef LOCAL
#define NDEBUG 1
#endif
#include<vector>
#include<cassert>
#include<set>
#include<string>
#include<algorithm>

#include<cstdio>
struct Input{
	auto& operator>>(char& it){
		while((it=(char)std::getchar())<=' ') {}
		return *this;
	}
	auto& operator>>(std::string& it){
		it.clear();
		char ch;
		do{
			while((ch=(char)std::getchar())>' ') it+=ch;
		}while(it.empty());
		return *this;
	}

	template<class T, class=std::enable_if<std::is_integral<T>::value>>
	auto& operator>>(T& it){
		using std::getchar;
		while((it=getchar())<'0') {}
		it-='0';
		int ch; while((ch=getchar())>='0') it=it*10+ch-'0';
		return *this;
	}

	auto& ignore(std::size_t number){
		while(number--) std::getchar();
		return *this;
	}
} cin;
struct Output{
	auto& operator<<(char it) {
		std::putchar(it); return *this;
	}
	auto& operator<<(int it) {
		std::printf("%d", it); return *this;
	}
	auto& operator<<(char const* it) {
		for(; *it; ++it) std::putchar(*it);
		return *this;
	}
} cout;

struct IntIterator{
	using iterator_category=std::forward_iterator_tag;
	using value_type=int;
	using difference_type=ptrdiff_t;
	using pointer=const int*;
	using reference=const int&;

	int stuff;
	int operator*()const{return stuff;}
	auto& operator++(){++stuff; return *this;}
	bool operator==(IntIterator other) const{return stuff==other.stuff;}
	bool operator!=(IntIterator other) const{return stuff!=other.stuff;}
};

/*
struct Tree{
	std::vector<std::vector<int>> data;
	Tree(int number): data(number, std::vector<int>(number)){}
	void add(int left1, int right1, int left2, int right2, int value){
		for(int i=left1; i<right1; ++i)
		for(int j=left2; j<right2; ++j)
			data[i][j]+=value;
	}
	int get(int i, int j) const{
		return data[i][j];
	}
	void build(){
		for(auto& it: data)for(auto& it: it) it=0;
	}
};
*/

struct Tree{
	std::vector<std::vector<int>> data, indices;

	Tree(int number): indices(number){}

	template<bool real>
	void addSuffix(int i, int j, int value){
		for(int i1=i; i1<(int)indices.size(); i1|=i1+1)
			if(real){
				auto const iterator=std::lower_bound(begin(indices[i1]), end(indices[i1]), j);
				assert(*iterator==j);

				for(int j1=
						int(iterator-indices[i1].begin())
						; j1<(int)data[i1].size(); j1|=j1+1)
					data[i1][j1]+=value;
			}else{
				indices[i1].push_back(j);
			}
	}
	template<bool real>
	void add(int left1, int right1, int left2, int right2, int value){
		addSuffix<real>(left1, left2, value);
		addSuffix<real>(left1, right2, -value);
		addSuffix<real>(right1, left2, -value);
		addSuffix<real>(right1, right2, value);
	}
	int get(int i, int j) const{
		int result{};
		for(int i1=i; i1>=0; i1=(i1&(i1+1))-1)
		for(int j1=
				int(std::upper_bound(begin(indices[i1]), end(indices[i1]), j)-indices[i1].begin())-1
				; j1>=0; j1=(j1&(j1+1))-1)
			result+=data[i1][j1];
		return result;
	}
	void build(){
		data.resize(indices.size());
		for(int index=0; index<(int)indices.size(); ++index){
			std::sort(begin(indices[index]), end(indices[index]));
			indices[index].resize(std::unique(begin(indices[index]), end(indices[index]))-indices[index].begin());
			data[index].resize(indices[index].size());
		}
	}
};

int main(){
	int number, numQuery; cin>>number>>numQuery;
	
	std::string start; start.reserve(number); cin>>start;
	struct Query{char type; int first, sec;};
	std::vector<Query> queries(numQuery);
	for(auto& [type, first, sec]: queries){
		cin>>type;
		cin.ignore(5);
		cin>>first;
		if(type=='q') cin>>sec;
		else assert(type=='t');
		--first; --sec;
	}


	Tree tree(number);

	auto const process=[&](auto real_){
		auto constexpr real=real_();

		std::set<int> zeroes(IntIterator{-1}, IntIterator{number+1});

		auto const toggle=[&](int index, int time){
			assert(time>0);
			auto [iterator, inserted]=zeroes.insert(index);
			if(inserted){
				tree.add<real>(*std::prev(iterator)+1, index+1, index, *std::next(iterator), time);
			}else{
				iterator=zeroes.erase(iterator);
				tree.add<real>(*std::prev(iterator)+1, index+1, index, *iterator, -time);
			}
		};

		for(int index=0; index<number; ++index)
			if(start[index]=='1') toggle(index, 1);

		for(int time=0; time<numQuery; ++time){
			auto const [type, first, sec]=queries[time];
			if(type=='q'){
				if(real){
					int const result=tree.get(first, sec-1);
					cout<<(result<0 ? result+time+2: result)<<'\n';
				}
			}else{
				toggle(first, time+2);
			}
		}
	};

	process(std::false_type{});
	tree.build();
	process(std::true_type{});
}

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