oj.uz

Submission #246292

# Submission time Handle Problem Language Result Execution time Memory
246292 2020-07-08T15:04:17 Z user202729 Street Lamps (APIO19_street_lamps) C++17
20 / 100
 5000 ms 287520 KB 
// how?...
#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;
	std::vector<std::set<int>> indicesSet;

	Tree(int number): indices(number), indicesSet(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);
				indicesSet[i1].insert(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());
			*/
			indices[index].assign(begin(indicesSet[index]), end(indicesSet[index]));
			indicesSet[index].clear();

			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 4 ms 256 KB Output is correct
3 Correct 5 ms 256 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 773 ms 8184 KB Output is correct
2 Correct 1357 ms 8696 KB Output is correct
3 Correct 3604 ms 14352 KB Output is correct
4 Execution timed out 5100 ms 287520 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 1152 KB Output is correct
2 Correct 15 ms 1024 KB Output is correct
3 Correct 15 ms 1024 KB Output is correct
4 Correct 16 ms 1280 KB Output is correct
5 Execution timed out 5077 ms 247248 KB Time limit exceeded
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 13 ms 896 KB Output is correct
3 Correct 16 ms 1024 KB Output is correct
4 Correct 20 ms 1024 KB Output is correct
5 Execution timed out 5104 ms 283032 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 4 ms 256 KB Output is correct
3 Correct 5 ms 256 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 773 ms 8184 KB Output is correct
9 Correct 1357 ms 8696 KB Output is correct
10 Correct 3604 ms 14352 KB Output is correct
11 Execution timed out 5100 ms 287520 KB Time limit exceeded
12 Halted 0 ms 0 KB -