oj.uz

Submission #249094

# Submission time Handle Problem Language Result Execution time Memory
249094 2020-07-14T10:13:09 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';
		}
		
		
	}
	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

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: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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14368 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 9 ms 14464 KB Output is correct
6 Correct 8 ms 14464 KB Output is correct
7 Correct 12 ms 14464 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 18936 KB Output is correct
2 Correct 102 ms 18968 KB Output is correct
3 Correct 115 ms 19576 KB Output is correct
4 Correct 257 ms 35724 KB Output is correct
5 Correct 287 ms 38156 KB Output is correct
6 Correct 204 ms 33544 KB Output is correct
7 Correct 407 ms 42248 KB Output is correct
8 Correct 398 ms 43660 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 8 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 Execution timed out 5068 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 14368 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 9 ms 14464 KB Output is correct
6 Correct 8 ms 14464 KB Output is correct
7 Correct 12 ms 14464 KB Output is correct
8 Correct 87 ms 18936 KB Output is correct
9 Correct 102 ms 18968 KB Output is correct
10 Correct 115 ms 19576 KB Output is correct
11 Correct 257 ms 35724 KB Output is correct
12 Correct 287 ms 38156 KB Output is correct
13 Correct 204 ms 33544 KB Output is correct
14 Correct 407 ms 42248 KB Output is correct
15 Correct 398 ms 43660 KB Output is correct
16 Correct 8 ms 14464 KB Output is correct
17 Incorrect 8 ms 14592 KB Output isn't correct
18 Halted 0 ms 0 KB -