oj.uz

Submission #733214

# Submission time Handle Problem Language Result Execution time Memory
733214 2023-04-30T09:03:12 Z minhcool Street Lamps (APIO19_street_lamps) C++17
20 / 100
 73 ms 12848 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';
				}
				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 1 ms 340 KB Output is correct
2 Correct 0 ms 212 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 1 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct

Subtask #2
0 / 20.0

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

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 1 ms 340 KB Output is correct
2 Correct 0 ms 212 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 1 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Incorrect 73 ms 12848 KB Output isn't correct
9 Halted 0 ms 0 KB -