oj.uz

Submission #733215

# Submission time Handle Problem Language Result Execution time Memory
733215 2023-04-30T09:04:38 Z minhcool Street Lamps (APIO19_street_lamps) C++17
40 / 100
 115 ms 20360 KB 
#include<bits/stdc++.h>
using namespace std;
 
// 60 is enough for gold lol, we got 2 ACs already
 
#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
 
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
 
const int N = 3e5 + 5;
 
const int oo = 1e18 + 7, mod = 1e9 + 7;
 
int n, q;
string s;
vector<pair<int, ii>> queries;
 
namespace solve_small{
	bool ck[105][105];
	void process(){
		for(int i = 1; i <= n; i++) ck[1][i] = (s[i - 1] != '0');
		for(int i = 1; i <= q; i++){
			for(int j = 1; j <= n; j++) ck[i + 1][j] = ck[i][j];
			if(queries[i - 1].fi == 1) ck[i + 1][queries[i - 1].se.fi] ^= 1;
			else{
				int ans = 0;
				for(int j = 1; j <= i; j++){
					int ckk = 1;
					for(int k = queries[i - 1].se.fi; k <= queries[i - 1].se.se; k++) ckk &= ck[j][k];
					ans += ckk;
				}
				cout << ans << "\n";
			}
		//	for(int j = 1; j <= n; j++) cout << ck[i][j];
			//cout << "\n";
		}
	}
}
 
namespace solve_eq{
	int lst[N];
	int tol_off[N];
	void process(){
		for(int i = 1; i <= n; i++) lst[i] = tol_off[i] = 0;
		for(int i = 1; i <= n; i++) if(s[i - 1] == '1') lst[i] = oo;
		for(int i = 1; i <= q; i++){
			if(queries[i - 1].fi == 1){
				if(s[queries[i - 1].se.fi - 1] == '0'){
					tol_off[queries[i - 1].se.fi] += i - lst[queries[i - 1].se.fi];
					lst[queries[i - 1].se.fi] = oo;
					s[queries[i - 1].se.fi - 1] = '1';
				}
				else{
					lst[queries[i - 1].se.fi] = i;
					s[queries[i - 1].se.fi - 1] = '0';
				}
			}
			else{
				int temp = tol_off[queries[i - 1].se.fi];
				temp += max(0LL, i - lst[queries[i - 1].se.fi]);
				cout << (i - temp) << "\n";
			}
		}
	}
}
 
namespace off_solve{
	void process(){
		
	}
}
 
void process(){
	cin >> n >> q;
	cin >> s;
	bool ck = 1;
	for(int i = 1; i <= q; i++){
		int type;
		string ss;
		cin >> ss;
		type = (ss == "toggle" ? 1 : 2);
		if(type == 1){
			int a;
			cin >> a;
			queries.pb({type, {a, -1}});
		}
		else{
			int a, b;
			cin >> a >> b;
			b--;
			ck &= (a == b);
			queries.pb({type, {a, b}});
		}
	}
	if(n <= 100 && q <= 100) solve_small::process();
	else if(ck) solve_eq::process();
	else off_solve::process();
}
 
signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	process();
}

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 12656 KB Output is correct
2 Correct 75 ms 15992 KB Output is correct
3 Correct 81 ms 16384 KB Output is correct
4 Correct 91 ms 18280 KB Output is correct
5 Correct 98 ms 18700 KB Output is correct
6 Correct 85 ms 18004 KB Output is correct
7 Correct 107 ms 19000 KB Output is correct
8 Correct 115 ms 20360 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 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 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 70 ms 12656 KB Output is correct
9 Correct 75 ms 15992 KB Output is correct
10 Correct 81 ms 16384 KB Output is correct
11 Correct 91 ms 18280 KB Output is correct
12 Correct 98 ms 18700 KB Output is correct
13 Correct 85 ms 18004 KB Output is correct
14 Correct 107 ms 19000 KB Output is correct
15 Correct 115 ms 20360 KB Output is correct
16 Incorrect 1 ms 340 KB Output isn't correct
17 Halted 0 ms 0 KB -