Submission #210022

#	Time	Username	Problem	Language	Result	Execution time	Memory
210022		mieszko11b	Street Lamps (APIO19_street_lamps)	C++14	60 / 100	5029 ms	298544 KiB

street_lamps

#include <bits/stdc++.h>

using namespace std;

using ii = pair<int, int>;

const int inf = 1e9;

#define X first
#define Y second

vector<ii> P;

int n, q;
char s[300007];
vector<ii> Q;

bool compy(ii a, ii b) {
	return (ii){a.Y, a.X} < (ii){b.Y, b.X};
}

struct SegmentTree1D {
	vector<ii> P;
	vector<int> d;
	int lv;
	
	SegmentTree1D(int L, int R) {
		lv = R - L + 1;
		d.resize(2 * lv + 3);
		P.resize(lv);
		for(int i = 0 ; i < lv ; i++)
			P[i] = ::P[L + i];
		sort(P.begin(), P.end(), compy);
	}
	
	void insert(int w, int l, int r, int miny, int v) {
		if(P[r].Y < miny)
			return ;
		if(P[l].Y >= miny) {
			//~ cout << "ins1d on " << l << " " << r << endl;
			d[w] += v;
			return ;
		}
		
		insert(2 * w, l, (l + r) / 2, miny, v);
		insert(2 * w + 1, (l + r) / 2 + 1, r, miny, v);
	}
	
	int query(int w, int l, int r, ii p) {
		if(w >= 2 * lv)
			return 0;
		if(P[l].Y > p.Y || (P[l].Y == p.Y && P[l].X > p.X))
			return 0;
		if(p.Y > P[r].Y || (p.Y == P[r].Y && p.X > P[r].X))
			return 0;
		
		int res = d[w];
		res += query(2 * w, l, (l + r) / 2, p);
		res += query(2 * w + 1, (l + r) / 2 + 1, r, p);
		return res;
	}
	
	void insert(int miny, int v) {
		insert(1, 0, lv - 1, miny, v);
	}
	
	int query(ii p) {
		return query(1, 0, lv - 1, p);
	}
};

struct SegmentTree2D {
	int lv;
	vector<SegmentTree1D*> d;
	
	void build(int w, int l, int r) {
		if(w >= 2 * lv)
			return ;
		d[w] = new SegmentTree1D(l, r);
		build(2 * w, l, (l + r) / 2);
		build(2 * w + 1, (l + r) / 2 + 1, r);
	}
	
	SegmentTree2D() {
		lv = 2;
		sort(P.begin(), P.end());
		P.resize(distance(P.begin(), unique(P.begin(), P.end())));
		
		while(lv < P.size())
			lv *= 2;
		while(P.size() < lv)
			P.push_back({inf, inf});
		
		d.resize(2 * lv + 3);
		build(1, 0, lv - 1);
	}
	
	void insert(int w, int l, int r, int maxx, int miny, int v) {
		if(P[l].X > maxx)
			return ;
		if(P[r].X <= maxx) {
			//~ cout << "ins2d on " << l << " " << r << endl;
			d[w]->insert(miny, v);
			return ;
		}
		insert(2 * w, l, (l + r) / 2, maxx, miny, v);
		insert(2 * w + 1, (l + r) / 2 + 1, r, maxx, miny, v);
	}
	
	int query(int w, int l, int r, ii p) {
		if(w >= 2 * lv)
			return 0;
		if(P[l] > p)
			return 0;
		if(p > P[r])
			return 0;
			
		int res = d[w]->query(p);
		res += query(2 * w, l, (l + r) / 2, p);
		res += query(2 * w + 1, (l + r) / 2 + 1, r, p);
		return res;
	}
	
	void insert(int maxx, int miny, int v) {
		//~ cout << "ins x<=" << maxx << " y>=" << miny << endl;
		insert(1, 0, lv - 1, maxx, miny, v);
	}
	
	int query(ii p) {
		return query(1, 0, lv - 1, p);
	}
};

SegmentTree2D *ST;
set<ii> segments;

void init_segments() {
	for(int i = 1 ; i <= n ; ) {
		int j = i;
		while(j <= n && s[j] == '1')
			j++;
		if(j > i)
			segments.insert({i, j - 1});
		i = j + 1;
	}
}

int query(ii p, int t) {
	bool active = false;
	auto it = segments.upper_bound({p.X, inf});
	if(it != segments.begin()) {
		it = prev(it);
		auto p2 = *it;
		if(p2.Y >= p.Y)
			active = true;
	}
	
	int v = ST->query(p);
	
	//~ cout << "query " << p.X <<  " " << p.Y << " " << active << " " << v << " " << t << endl;
	
	if(active)
		v += t;
	return v;
}

void tree_insert(int a, int b, int c, int d, int v) {
	//~ cout << "ins" << a << " "  << b <<  " " << c << " " << d << " " << v << endl;
	ST->insert(b, c, v);
	ST->insert(a - 1, c, -v);
	ST->insert(b, d + 1, -v);
	ST->insert(a - 1, d + 1, v);
}

void light_up(int i, int t) {
	auto rightit = segments.upper_bound((ii){i, inf});
	auto leftit = segments.end();
	if(rightit != segments.begin())
		leftit = prev(rightit);
		
	ii left = {-inf, -inf}, right = {inf, inf};
	if(rightit != segments.end()) right = *rightit;
	if(leftit != segments.end()) left = *leftit;
	
	if(left.Y == i - 1 && right.X == i + 1) {
		tree_insert(left.X, i, i, right.Y, -t);
		segments.erase(left);
		segments.erase(right);
		segments.insert({left.X, right.Y});
	} else if(left.Y == i - 1) {
		tree_insert(left.X, i, i, i, -t);
		segments.erase(left);
		segments.insert({left.X, i});
	} else if(right.X == i + 1) {
		tree_insert(i, i, i, right.Y, -t);
		segments.erase(right);
		segments.insert({i, right.Y});
	} else {
		tree_insert(i, i, i, i, -t);
		segments.insert({i, i});
	}
}

void light_down(int i, int t) {
	auto it = segments.upper_bound((ii){i, inf});
	it = prev(it);
	ii seg = *it;
	
	tree_insert(seg.X, i, i, seg.Y, t);
	segments.erase(seg);
	if(seg.X <= i - 1)
		segments.insert({seg.X, i - 1});
	if(i + 1 <= seg.Y)
		segments.insert({i + 1, seg.Y});
}

void toggle(int i, int t) {
	if(s[i] == '1') {
		s[i] = '0';
		light_down(i, t);
	} else {
		s[i] = '1';
		light_up(i, t);
	}
}

int main() {
	scanf("%d%d", &n, &q);
	scanf(" %s", s + 1);
	
	for(int i = 0 ; i < q ; i++) {
		char comm[10];
		scanf(" %s", comm);
		if(comm[0] == 't') {
			int i;
			scanf("%d", &i);
			Q.emplace_back(i, -1);
		} else {
			int a, b;
			scanf("%d%d", &a, &b);
			Q.emplace_back(a, b);
			P.push_back({a, b - 1});
		}
	}

	ST = new SegmentTree2D();
	
	//~ for(auto p : P)
		//~ cout << p.X << " " << p.Y << "; " ;
	//~ cout << endl;
	init_segments();
	
	int t = 1;
	for(auto q : Q) {
		//~ cout << "S: ";
		//~ for(auto p : segments)
			//~ cout << p.X << " " << p.Y << "; ";
		//~ cout << endl;
		
		if(q.Y == -1)
			toggle(q.X, t);
		else
			printf("%d\n", query({q.X, q.Y - 1}, t));
		t++;
	}
	
	return 0;
}

Compilation message (stderr)

street_lamps.cpp: In constructor 'SegmentTree2D::SegmentTree2D()':
street_lamps.cpp:89:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(lv < P.size())
         ~~~^~~~~~~~~~
street_lamps.cpp:91:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(P.size() < lv)
         ~~~~~~~~~^~~~
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:228:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &q);
  ~~~~~^~~~~~~~~~~~~~~~
street_lamps.cpp:229:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf(" %s", s + 1);
  ~~~~~^~~~~~~~~~~~~~
street_lamps.cpp:233:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %s", comm);
   ~~~~~^~~~~~~~~~~~~
street_lamps.cpp:236:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &i);
    ~~~~~^~~~~~~~~~
street_lamps.cpp:240:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d%d", &a, &b);
    ~~~~~^~~~~~~~~~~~~~~~

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