oj.uz

Submission #249076

# Submission time Handle Problem Language Result Execution time Memory
249076 2020-07-14T09:47:50 Z crossing0ver Street Lamps (APIO19_street_lamps) C++17
20 / 100
 76 ms 4856 KB 
#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[x] + (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

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

Subtask #1
20.0 / 20.0

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

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 76 ms 4856 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Incorrect 76 ms 4856 KB Output isn't correct
9 Halted 0 ms 0 KB -