oj.uz

Submission #824006

# Submission time Handle Problem Language Result Execution time Memory
824006 2023-08-13T11:23:34 Z Mohammed_Atalah Street Lamps (APIO19_street_lamps) C++17
20 / 100
 187 ms 19224 KB 
/// Template path: /home/mohammed/.config/sublime-text-3/Packages/User

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;

// typedef
typedef long long ll;
typedef long double ld;
typedef vector<int> vecint;
typedef vector<char> vecchar;
typedef vector<string> vecstr;
typedef vector<long long> vecll;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

// Marcos
#define endl ("\n")
#define int long long
#define mod 1000000007
#define pi (3.141592653589)
#define REP(i,a,b) for (int i = a; i < b; i++)
#define RREP(i,a,b) for (int i = a; i > b; i--)
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)

// Functions
long long squared(long long x) {return (x * x) % mod;}
int factorial(int n) {long long res = 1; for (int i = 1; i <= n; i++) {res = ((res * i) % mod + mod) % mod ;} return res;}
long long power(long long x, long long p) {if (p == 0) {return 1;} if (p % 2 == 1) {return (power(x, p - 1) * x) % mod;} return squared(power(x, p / 2));}

// cout << fixed;
// cout << setprecision(4);


// ---------(^_^)--------- //


struct segtree {

	int size = 1;

	vector<int> mx;
	void init(int n) {
		while (size < n)size *= 2;
		mx.assign(2 * size, -1);

	}

	void build(vector<int>&v, int x, int  lx, int rx) {
		if (rx - lx == 1) {
			if (lx < v.size()) {
				mx[x] = v[lx];
			}
			return;
		}

		int m = (lx + rx) / 2;
		build(v, 2 * x + 1, lx, m);
		build(v, 2 * x + 2, m, rx);
		mx[x] = max(mx[2 * x + 1] , mx[2 * x + 2]);
	}

	void build(vector<int> &v) {
		build(v, 0, 0, size);
	}


	void set(int i, int v, int x, int lx, int rx) {
		if (rx - lx == 1) {
			mx[x] = v;
			return;
		}

		int m = (lx + rx) / 2;

		if (i < m) {
			set(i, v, x * 2 + 1, lx, m);
		} else {
			set(i, v, x * 2 + 2, m, rx);
		}

		mx[x] = max(mx[2 * x + 1] , mx[2 * x + 2]);
	}

	void set(int i, int v) {
		set(i, v, 0, 0, size);
	}


	int maxel (int l, int r, int x, int lx, int rx) {
		if (rx <= l || r <= lx )return -1;
		if (l <= lx && rx <= r) return mx[x];
		int m = (rx + lx) / 2;
		int n1 = maxel(l, r, x * 2 + 1, lx, m );
		int n2 = maxel(l, r, x * 2 + 2, m, rx );
		return max(n1 , n2);

	}

	int maxel(int l, int r) {
		return maxel(l, r, 0, 0, size);
	}



};



void main_solve() {
	int n, q; cin >> n >> q;
	string s; cin >> s;
	int we = q + 2;
	vector<int> v(n, we);
	for (int i = 0; i < n ; i ++) {
		if (s[i] == '1') {
			v[i] = 0;
		}
	}

	segtree st;
	st.init(n);
	st.build(v);
	int curr_time = 0;
	while (q--) {
		curr_time++;
		string type; cin >> type;

		if (type == "toggle") {
			int x; cin >> x;
			st.set(x - 1, curr_time);
		} else {
			int a, b; cin >> a >> b;
			int e = st.maxel(a - 1, b - 1);
			if (e  > curr_time) {
				cout << 0 << endl;
			} else {
				cout << curr_time - e << endl;
			}
		}



	}





}


int32_t main() {

	fast;
// #ifndef ONLINE_JUDGE
// 	freopen("input.txt", "r", stdin);
// 	freopen("output.txt", "w", stdout);
// #endif
	// Just another problem (-_-)

	int t;
	t = 1;
	// cin >> t;

	while (t--) {
		main_solve();
	}


}

Compilation message

street_lamps.cpp: In member function 'void segtree::build(std::vector<long long int>&, long long int, long long int, long long int)':
street_lamps.cpp:52:11: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |    if (lx < v.size()) {
      |        ~~~^~~~~~~~~~

Subtask #1
0 / 20.0

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

Subtask #2
0 / 20.0

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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 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 90 ms 15512 KB Output is correct
6 Correct 119 ms 16160 KB Output is correct
7 Correct 151 ms 16876 KB Output is correct
8 Correct 185 ms 19172 KB Output is correct
9 Correct 73 ms 3876 KB Output is correct
10 Correct 75 ms 4252 KB Output is correct
11 Correct 76 ms 4504 KB Output is correct
12 Correct 174 ms 17724 KB Output is correct
13 Correct 187 ms 19224 KB Output is correct

Subtask #4
0 / 20.0

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

Subtask #5
0 / 20.0

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