Submission #249073

#	Time	Username	Problem	Language	Result	Execution time	Memory
249073		crossing0ver	Street Lamps (APIO19_street_lamps)	C++17	20 / 100	70 ms	9720 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),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+1)-last[x];
				last[x] = i+1;
			}
			else {
				last[x] = i; // or i+1 
			}
			s[x] = (!s[x]);
		}
		else {
			int x = quest[i].a;
			cout << ans[i] + (s[x] ? (i + 1) - last[x] : 0) <<'\n';
		}
		
		
		
	}
	
	
	
}

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;
	for (int i = 0,x; i < q; i++) {
		cin >> tp;
	if (tp[0] == 't') {
		quest[i].type = 0;
		 cin >> x;
		 x--;
		 quest[i].a = x;
	}
	else {
		quest[i].type = 1;
		cin >> quest[i].a >> quest[i].b;
		quest[i].a--;
		quest[i].b-=2;
		if (quest[i].a != quest[i].b)
				flag = 0;
	}
	}
	if (flag == 1) CaseAdj();
	
}

Compilation message (stderr)

street_lamps.cpp:70:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:73:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < S.size(); i++)
                  ~~^~~~~~~~~~

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