oj.uz

Submission #447872

# Submission time Handle Problem Language Result Execution time Memory
447872 2021-07-27T22:36:08 Z AmShZ Street Lamps (APIO19_street_lamps) C++17
20 / 100
 5000 ms 311212 KB 
//khodaya khodet komak kon
# include <bits/stdc++.h>
/*
# pragma GCC optimize("Ofast,unroll-loops")
# pragma comment(linker, "/stack:200000000")
# pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma,tune=native")
*/

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;
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)
			//if (fen[x].find(i) != fen[x].end())
			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 8 ms 14412 KB Output is correct
2 Correct 8 ms 14384 KB Output is correct
3 Correct 9 ms 14404 KB Output is correct
4 Correct 10 ms 14540 KB Output is correct
5 Correct 10 ms 14524 KB Output is correct
6 Correct 10 ms 14540 KB Output is correct
7 Correct 9 ms 14540 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2207 ms 15932 KB Output is correct
2 Correct 2816 ms 16352 KB Output is correct
3 Correct 4836 ms 25552 KB Output is correct
4 Execution timed out 5085 ms 309784 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 15820 KB Output is correct
2 Correct 42 ms 15988 KB Output is correct
3 Correct 38 ms 16196 KB Output is correct
4 Correct 28 ms 16400 KB Output is correct
5 Execution timed out 5077 ms 311212 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 16336 KB Output is correct
2 Correct 35 ms 16340 KB Output is correct
3 Correct 39 ms 16104 KB Output is correct
4 Correct 45 ms 15836 KB Output is correct
5 Execution timed out 5054 ms 308524 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14412 KB Output is correct
2 Correct 8 ms 14384 KB Output is correct
3 Correct 9 ms 14404 KB Output is correct
4 Correct 10 ms 14540 KB Output is correct
5 Correct 10 ms 14524 KB Output is correct
6 Correct 10 ms 14540 KB Output is correct
7 Correct 9 ms 14540 KB Output is correct
8 Correct 2207 ms 15932 KB Output is correct
9 Correct 2816 ms 16352 KB Output is correct
10 Correct 4836 ms 25552 KB Output is correct
11 Execution timed out 5085 ms 309784 KB Time limit exceeded
12 Halted 0 ms 0 KB -