oj.uz

Submission #246285

# Submission time Handle Problem Language Result Execution time Memory
246285 2020-07-08T14:57:43 Z user202729 Street Lamps (APIO19_street_lamps) C++17
20 / 100
 5000 ms 524292 KB 
//oj.uz/problem/view/APIO19_street_lamps
//already.
#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){}

	int& getReference(int i, int j){
		auto const iterator=std::lower_bound(begin(indices[i]), end(indices[i]), j);
		assert(*iterator==j);
		return data[i][iterator-indices[i].begin()];
	}
	int getValue(int i, int j)const{
		auto const iterator=std::lower_bound(begin(indices[i]), end(indices[i]), j);
		if(iterator==indices[i].end() or *iterator!=j) return 0;
		return data[i][iterator-indices[i].begin()];
	}

	template<bool real>
	void addSuffix(int i, int j, int value){
		for(int i1=i; i1<(int)indices.size(); i1|=i1+1)
		for(int j1=j; j1<(int)indices.size(); j1|=j1+1)
			if(real){
				getReference(i1, j1)+=value;
			}else{
				indices[i1].push_back(j1);
			}
	}
	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=j; j1>=0; j1=(j1&(j1+1))-1)
			result+=getValue(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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 256 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 6 ms 384 KB Output is correct
6 Correct 6 ms 256 KB Output is correct
7 Correct 6 ms 384 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 756 ms 49604 KB Output is correct
2 Correct 1241 ms 76516 KB Output is correct
3 Correct 2998 ms 144080 KB Output is correct
4 Runtime error 1339 ms 524288 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1024 KB Output is correct
2 Correct 15 ms 1152 KB Output is correct
3 Correct 14 ms 1024 KB Output is correct
4 Correct 16 ms 1280 KB Output is correct
5 Runtime error 1702 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 896 KB Output is correct
2 Correct 12 ms 1024 KB Output is correct
3 Correct 16 ms 1152 KB Output is correct
4 Correct 18 ms 1280 KB Output is correct
5 Execution timed out 5083 ms 356752 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 256 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 6 ms 384 KB Output is correct
6 Correct 6 ms 256 KB Output is correct
7 Correct 6 ms 384 KB Output is correct
8 Correct 756 ms 49604 KB Output is correct
9 Correct 1241 ms 76516 KB Output is correct
10 Correct 2998 ms 144080 KB Output is correct
11 Runtime error 1339 ms 524288 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Halted 0 ms 0 KB -