oj.uz

Submission #447851

# Submission time Handle Problem Language Result Execution time Memory
447851 2021-07-27T20:46:52 Z AmShZ Street Lamps (APIO19_street_lamps) C++11
20 / 100
 5000 ms 497640 KB 
//khodaya khodet komak kon
#pragma GCC optimize("Ofast")
# include <bits/stdc++.h>

using namespace std;

typedef long long                                        ll;
typedef long double                                      ld;
typedef pair <int, int>                                  pii;
typedef pair <pii, int>                                  ppi;
typedef pair <int, pii>                                  pip;
typedef pair <pii, pii>                                  ppp;
typedef pair <ll, ll>                                    pll;

# define A                                               first
# define B                                               second
# define endl                                            '\n'
# define sep                                             ' '
# define all(x)                                          x.begin(), x.end()
# define kill(x)                                         return cout << x << endl, 0
# define SZ(x)                                           int(x.size())
# define lc                                              id << 1
# define rc                                              id << 1 | 1
# define fast_io                                         ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);

ll power(ll a, ll b, ll md) {return (!b ? 1 : (b & 1 ? a * power(a * a % md, b / 2, md) % md : power(a * a % md, b / 2, md) % md));}

const int xn = 3e5 + 10;
const int xm = - 20 + 10;
const int sq = 320;
const int inf = 1e9 + 10;
const ll INF = 1e18 + 10;
const ld eps = 1e-15;
const int mod = 998244353;
const int base = 257;

int n, q;
unordered_map <int, int> fen[xn];
string S;
set <int> st;
bool fl[xn];

void mofen(int x, int y, int val){
	int ly = y;
	for (x += 5; x < xn; x += x & - x){
		y = ly;
		for (y += 5; y < xn; y += y & - y)
			fen[x][y] += val;
	}
}
int gefen(int x, int y){
	int res = 0, ly = y;
	for (x += 5; 0 < x; x -= x & - x){
		y = ly;
		for (y += 5; 0 < y; y -= y & - y)
			res += fen[x][y];
	}
	return res;
}
void upd(int l1, int r1, int l2, int r2, int val){
	mofen(l1, l2, val);
	mofen(l1, r2 + 1, - val);
	mofen(r1 + 1, l2, - val);
	mofen(r1 + 1, r2 + 1, val);
}

int main(){
	fast_io;

	cin >> n >> q >> S;
	S = '.' + S;
	st.insert(0);
	st.insert(n + 1);
	int last = n + 1;
	for (int i = n; 1 <= i; -- i){
		if (S[i] == '0')
			last = i, st.insert(i);
		fl[i] = S[i] - '0';
		upd(i - 1, i - 1, i - 1, last - 1, q);
	}
	for (int i = 1; i <= q; ++ i){
		int l, r, ind;
		cin >> S;
		if (S[0] == 't'){
			cin >> ind;
			if (!fl[ind]){
				int y = *st.lower_bound(ind + 1);
				int x = *prev(st.lower_bound(ind));
				upd(x, ind - 1, ind, y - 1, q - i);
				st.erase(ind);
			}
			else{
				int y = *st.lower_bound(ind + 1);
				int x = *prev(st.lower_bound(ind));
				upd(x, ind - 1, ind, y - 1, i - q);
				st.insert(ind);
			}
			fl[ind] ^= 1;
		}
		else{
			cin >> l >> r;
			int ans = gefen(l - 1, r - 1);
			if (r <= *st.lower_bound(l))
				ans -= q - i;
			cout << ans << endl;
		}
	}

	return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 16732 KB Output is correct
2 Correct 12 ms 16764 KB Output is correct
3 Correct 13 ms 16804 KB Output is correct
4 Correct 15 ms 16924 KB Output is correct
5 Correct 15 ms 16900 KB Output is correct
6 Correct 13 ms 16820 KB Output is correct
7 Correct 14 ms 16936 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2827 ms 17920 KB Output is correct
2 Correct 2500 ms 18496 KB Output is correct
3 Correct 3292 ms 26504 KB Output is correct
4 Execution timed out 5078 ms 363004 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 18124 KB Output is correct
2 Correct 43 ms 18244 KB Output is correct
3 Correct 39 ms 18416 KB Output is correct
4 Correct 32 ms 18500 KB Output is correct
5 Execution timed out 5083 ms 301940 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 18520 KB Output is correct
2 Correct 37 ms 18464 KB Output is correct
3 Correct 50 ms 18228 KB Output is correct
4 Correct 51 ms 18140 KB Output is correct
5 Execution timed out 5087 ms 497640 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 16732 KB Output is correct
2 Correct 12 ms 16764 KB Output is correct
3 Correct 13 ms 16804 KB Output is correct
4 Correct 15 ms 16924 KB Output is correct
5 Correct 15 ms 16900 KB Output is correct
6 Correct 13 ms 16820 KB Output is correct
7 Correct 14 ms 16936 KB Output is correct
8 Correct 2827 ms 17920 KB Output is correct
9 Correct 2500 ms 18496 KB Output is correct
10 Correct 3292 ms 26504 KB Output is correct
11 Execution timed out 5078 ms 363004 KB Time limit exceeded
12 Halted 0 ms 0 KB -