oj.uz

Submission #249092

# Submission time Handle Problem Language Result Execution time Memory
249092 2020-07-14T10:10:42 Z crossing0ver Street Lamps (APIO19_street_lamps) C++17
40 / 100
 452 ms 43780 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,-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';
		}
		
		
	}
	
	
	
}
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();
	
}

Compilation message

street_lamps.cpp: In function 'void Case3()':
street_lamps.cpp:91:9: warning: pointer to a function used in arithmetic [-Wpointer-arith]
    add[x];
         ^
street_lamps.cpp:91:9: warning: value computed is not used [-Wunused-value]
    add[x];
    ~~~~~^
street_lamps.cpp:91:9: warning: statement has no effect [-Wunused-value]
street_lamps.cpp: At global scope:
street_lamps.cpp:117:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:120: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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 14464 KB Output is correct
2 Correct 9 ms 14464 KB Output is correct
3 Correct 8 ms 14464 KB Output is correct
4 Correct 11 ms 14464 KB Output is correct
5 Correct 8 ms 14464 KB Output is correct
6 Correct 12 ms 14464 KB Output is correct
7 Correct 11 ms 14464 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 18936 KB Output is correct
2 Correct 106 ms 18936 KB Output is correct
3 Correct 117 ms 19524 KB Output is correct
4 Correct 265 ms 35724 KB Output is correct
5 Correct 288 ms 38028 KB Output is correct
6 Correct 220 ms 33548 KB Output is correct
7 Correct 452 ms 42376 KB Output is correct
8 Correct 425 ms 43780 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14464 KB Output is correct
2 Incorrect 9 ms 14592 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

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

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 14464 KB Output is correct
2 Correct 9 ms 14464 KB Output is correct
3 Correct 8 ms 14464 KB Output is correct
4 Correct 11 ms 14464 KB Output is correct
5 Correct 8 ms 14464 KB Output is correct
6 Correct 12 ms 14464 KB Output is correct
7 Correct 11 ms 14464 KB Output is correct
8 Correct 94 ms 18936 KB Output is correct
9 Correct 106 ms 18936 KB Output is correct
10 Correct 117 ms 19524 KB Output is correct
11 Correct 265 ms 35724 KB Output is correct
12 Correct 288 ms 38028 KB Output is correct
13 Correct 220 ms 33548 KB Output is correct
14 Correct 452 ms 42376 KB Output is correct
15 Correct 425 ms 43780 KB Output is correct
16 Correct 8 ms 14464 KB Output is correct
17 Incorrect 9 ms 14592 KB Output isn't correct
18 Halted 0 ms 0 KB -