Submission #249095

#	Time	Username	Problem	Language	Result	Execution time	Memory
249095		crossing0ver	Street Lamps (APIO19_street_lamps)	C++17	60 / 100	5044 ms	56744 KiB

street_lamps

#include<bits/stdc++.h>
#define pb push_back
#define ll long long
using namespace std;
const int N = 3e5+5;
int n,q;
string S;
bool s[N];
void Small() {
	string type;
	vector<int> Q;
	Q.pb(-1);
	for (int rep = 0,a,b,x; rep < q; rep++) {
		cin >> type;
		if (type[0] == 't') {
			 cin >> x;
			 x--;
			Q.pb(x);
		}
		else {
			cin >> a >> b;
			a--; b-=2;
			int ans = 0;
			for (int i : Q) {
				if (i != -1 ) s[i] = (!s[i]);
				bool flag = 1;
				for (int i = a; i <= b; i++) if (s[i] == 0) flag = 0;
				if (flag) ans++;
			}
			for (int i : Q) if (i != -1) s[i] = (!s[i]);
			cout << ans <<'\n';
			Q.pb(-1);
		}
	}
	exit(0);
}
struct {
	bool type;
	int a,b;
	
}quest[N];

void CaseAdj() {
	vector<int> last(n+1,-1),ans(n+1);
	for (int i = 0; i < q;i++) {
		if (quest[i].type == 0) {
			int x = quest[i].a;
			if (s[x] == 1) {
				ans[x] += i -last[x];
			}
			else {
				last[x] = i; // or i+1 
			}
			s[x] = (!s[x]);
		}
		else {
			int x = quest[i].a;
			cout << ans[x] + (s[x] ? i - last[x] : 0) <<'\n';
		}
	}
	exit(0);
}

set<int> L[N];
int vis[N],bit[N];
map<pair<int,int>,int> last;

void add(int pos) {
	for (++pos;pos < N; pos += pos & -pos)	
		bit[pos]++;
}
int get(int pos) {
	int s = 0;
	for (++pos;pos;pos-=pos&-pos)
		s+= bit[pos];
	return s;
}
int get(int l,int r)
{
	return get(r) - get(l-1);
}

void Case3() {
	for (int i = 0; i < n; i++) 
	if (s[i]) add(i);
	for (int rep = 0;rep < q ; rep ++) {
		if (quest[rep].type == 0) {
			int x = quest[rep].a;
			assert(s[x] == 0);
			s[x] = 1;
			add(x);
			int R;
			for (int i = x; i < n && s[i] == 1; i++) {
				R = i;
			}
			for (int i = x; i >= 0 && s[i] == 1; i--) {
				for (int b : L[i]) {
					if (b >= x && b <= R) {
						last[{i,b}] = rep;
					}
				}
			}
		}
		else {
			int x = quest[rep].a, y = quest[rep].b;
			if ((get(x,y)) == y-x+1)
			cout <<  rep - last[{x,y}]  <<'\n';
			else cout << 0 <<'\n';
		}
		
		
	}
	exit(0);
	
	
	
}
main() {
	ios::sync_with_stdio(0);
	cin >> n >> q >> S;
	for (int i = 0; i < S.size(); i++)
	s[i] = (S[i] == '1');
	if (n <= 100 && q <= 100) 
		Small();
	string tp;
	
	bool flag = 1,fl = 1;
	for (int i = 0,x; i < q; i++) {
		cin >> tp;
	if (tp[0] == 't') {
		quest[i].type = 0;
		 cin >> x;
		 x--;
		 if (vis[x]) fl = 0;
		 vis[x] = 1;
		 if (s[x] == 1) fl = 0;
		 quest[i].a = x;
	}
	else {
		quest[i].type = 1;
		cin >> quest[i].a >> quest[i].b;
		quest[i].a--;
		quest[i].b-=2;
		last[{quest[i].a,quest[i].b}] = -1;
		if (quest[i].a != quest[i].b)
				flag = 0;
		L[quest[i].a].insert(quest[i].b);
	}
	}
	if (flag == 1) CaseAdj();
	if (fl) Case3();
	while(true){
		
	}
	
}

Compilation message (stderr)

street_lamps.cpp:118:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:121:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < S.size(); i++)
                  ~~^~~~~~~~~~
street_lamps.cpp: In function 'void Case3()':
street_lamps.cpp:98:17: warning: 'R' may be used uninitialized in this function [-Wmaybe-uninitialized]
      if (b >= x && b <= R) {
          ~~~~~~~^~~~~~~~~

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