oj.uz

Submission #249093

# Submission time Handle Problem Language Result Execution time Memory
249093 2020-07-14T10:11:37 Z crossing0ver Street Lamps (APIO19_street_lamps) C++17
40 / 100
 5000 ms 43660 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();
	while(true){
		
	}
	
}

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 8 ms 14464 KB Output is correct
2 Correct 8 ms 14464 KB Output is correct
3 Correct 9 ms 14464 KB Output is correct
4 Correct 9 ms 14464 KB Output is correct
5 Correct 8 ms 14464 KB Output is correct
6 Correct 11 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 96 ms 19064 KB Output is correct
2 Correct 104 ms 18936 KB Output is correct
3 Correct 116 ms 19576 KB Output is correct
4 Correct 276 ms 35724 KB Output is correct
5 Correct 281 ms 38028 KB Output is correct
6 Correct 194 ms 33548 KB Output is correct
7 Correct 409 ms 42396 KB Output is correct
8 Correct 405 ms 43660 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5068 ms 14464 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5065 ms 14592 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14464 KB Output is correct
2 Correct 8 ms 14464 KB Output is correct
3 Correct 9 ms 14464 KB Output is correct
4 Correct 9 ms 14464 KB Output is correct
5 Correct 8 ms 14464 KB Output is correct
6 Correct 11 ms 14464 KB Output is correct
7 Correct 11 ms 14464 KB Output is correct
8 Correct 96 ms 19064 KB Output is correct
9 Correct 104 ms 18936 KB Output is correct
10 Correct 116 ms 19576 KB Output is correct
11 Correct 276 ms 35724 KB Output is correct
12 Correct 281 ms 38028 KB Output is correct
13 Correct 194 ms 33548 KB Output is correct
14 Correct 409 ms 42396 KB Output is correct
15 Correct 405 ms 43660 KB Output is correct
16 Execution timed out 5068 ms 14464 KB Time limit exceeded
17 Halted 0 ms 0 KB -