oj.uz

Submission #255208

# Submission time Handle Problem Language Result Execution time Memory
255208 2020-07-31T14:29:19 Z Atalasion Street Lamps (APIO19_street_lamps) C++14
20 / 100
 1624 ms 205684 KB 
//khodaya khodet komak kon
#include <bits/stdc++.h>

#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")


using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int N = 300000 + 10;
const ll MOD = 1000000000 + 7;
const ll INF = 1000000010;
const ll LOG = 25;

int koj[LOG][N], n, q, a[N], F[N], R[N];
vi seg[N << 2],fen[N << 2], L[N];
set<int> One, Zero;

bool cmp(int x, int y){
	return R[x] < R[y];
}

inline void add(int ind, int id, int x){
	for (; id < fen[ind].size(); id += id & (-id)) fen[ind][id] += x;
}

inline int get(int ind, int id){
	int res = 0;
	for (; id > 0; id -= id & (-id)) res += fen[ind][id];
	return res;
}

void build(int h, int id, int l, int r){
	if (r - l == 1){
		fen[id].pb(0);
		for (auto u:L[l]) seg[id].pb(u), fen[id].pb(0);
		sort(all(seg[id]), cmp);
//		cout << "Seg " << l << ' ' << r - 1<<'\n';
//		for (auto u:seg[id]) cout << R[u] << ' ';
		for (int i = 0; i < seg[id].size(); i++) koj[h][seg[id][i]] = i + 1;
	//	cout << '\n';
  		return;
	}
	int md = (l + r) >> 1;
	build(h + 1, id << 1, l, md);
	build(h + 1, id << 1 |1 , md, r);
	fen[id].pb(0);
	for (auto u:seg[id << 1]) seg[id].pb(u), fen[id].pb(0);
	for(auto u:seg[id << 1 | 1]) seg[id].pb(u), fen[id].pb(0);
	sort(all(seg[id]), cmp);
	for (int i = 0; i < seg[id].size(); i++) koj[h][seg[id][i]] = i + 1;
//	cout << "Seg " << l << ' ' << r - 1 <<'\n';
//	for (auto u:seg[id]) cout << R[u] << ' ';
//	cout << '\n';
  		
}

void Add(int id, int lq, int rq, int x, int t, int l, int r){
	if (rq <= l || r <= lq) return;
	if (lq <= l && r <= rq){
		if (seg[id].size() == 0) return;
		int LL = 0, RR = seg[id].size();
		if (R[seg[id][0]] >= x) return;
		while (RR - LL > 1){
			int md = (LL + RR) >> 1;
			if (R[seg[id][0]] < x) LL = md;
			else RR = md;
		}
		int zar = 1;
		add(id, 1, t);
		add(id, r + 1, -t);
		return;
	}
	int md = (l + r) >> 1;
	Add(id << 1, lq, rq, x, t, l, md);
	Add(id << 1 | 1, lq, rq, x, t, md, r);
}

void Add2(int id, int lq, int rq, int x, int t, int l, int r){
	if (rq <= l || r <= lq) return;
	if (lq <= l && r <= rq){
		if (seg[id].size() == 0) return;
		if (R[seg[id].back()] < x) return;
		int LL = -1, RR = seg[id].size() - 1;
		while (RR - LL > 1){
			int md = (RR + LL) >> 1;
			if (R[seg[id][md]] >= x) RR = md;
			else LL = md;
		}
//		cout << "Query\n";
//		cout << l << ' ' << r - 1 << ' ' << RR + 1 << ' ' << x << ' ';
		add(id, RR + 1, t);
//		cout << get(id, fen[id].size() - 1) << '\n';
		return;
	}
	int md = (l + r) >> 1;
	Add2(id << 1, lq, rq, x, t, l, md);
	Add2(id << 1 | 1, lq, rq, x, t, md, r);
}

int Get(int h, int id, int lq, int rq, int x, int l, int r){
	if (rq <= l || r <= lq)return 0;
	if (lq <= l && r <= rq){
//		cout << l << ' ' << r - 1 << ' ' << x << ' ' << koj[h][x] << ' ' << get(id, koj[h][x]) << '\n';
		return get(id, koj[h][x]);
	}
	int res = get(id, koj[h][x]);
//	cout << l << ' ' << r - 1 << ' ' << x << ' ' << koj[h][x] << ' ' <<res << '\n';
	int md = (l + r) >> 1;
	return (res + Get(h + 1, id << 1, lq, rq, x, l, md) + Get(h + 1, id << 1 | 1, lq, rq, x, md, r));
}

vector<pair<int, pii>> Q;

int32_t main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> q;
	string s;
	cin >> s;
	Zero.insert(0);
	Zero.insert(n + 1);
	One.insert(0), One.insert(n + 1);
	for (int i = 1; i <= n; i++) a[i] = (s[i - 1] == '1');
	for (int i = 1; i <= n; i++){
		if (a[i] == 1) One.insert(i);
		else Zero.insert(i);
	}
	for (int i = 1; i <= q; i++){
		cin >> s;
		if (s == "query"){
			int l, r;
			cin >> l >> r;
			r--;
			R[i] = r;
			L[l].pb(i);
			Q.pb({1, {l, r}});
		}else{
			int x;
			cin >> x;
			Q.pb({2, {x, 0}});
		}
	}
	build(0, 1, 1, n + 1);
	for (int i = 1; i <= q; i++){
		auto u = Q[i - 1];
		int x = u.F;
		if (x == 1){
			int l = u.S.F, r = u.S.S;
			int res = Get(0, 1, l, l + 1, i, 1, n + 1);
			if (a[l] == 1){
				auto koj = Zero.lower_bound(l);
				if ((*koj) > r) res += i;
			} 
			cout << res << '\n';
		}else{
			int l = u.S.F;
			if (a[l] == 1){
				a[l] = 0;
				One.erase(l);
				auto koj = Zero.lower_bound(l);
				auto koj2 = koj;
				koj2--;
//				cout << (*koj2) + 1 << ' ' << l << ' ' << (*koj) << endl;
//				cout << "YES" << endl;
				Add(1, (*koj2) + 1, l + 1, (*koj), i, 1, n + 1);
//				cout << "YES2" << endl;
				Add(1, (*koj2) + 1, l + 1, l, -i, 1, n + 1);
				Zero.insert(l);
			}else{
				a[l] = 1;
				Zero.erase(l);
				auto koj = Zero.lower_bound(l);
				auto koj2 = koj;
				koj2--;
//				cout << "Fuck " << (*koj2) + 1 << ' ' << (*koj) << '\n';
				Add2(1, (*koj2) + 1, l + 1, l, -i, 1, n + 1);
				Add2(1, (*koj2) + 1, l + 1, (*koj), i, 1, n + 1);
				One.insert(l);
			
			}
		}
	}









	return 0;
}

Compilation message

street_lamps.cpp: In function 'void add(int, int, int)':
street_lamps.cpp:31:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (; id < fen[ind].size(); id += id & (-id)) fen[ind][id] += x;
         ~~~^~~~~~~~~~~~~~~~~
street_lamps.cpp: In function 'void build(int, int, int, int)':
street_lamps.cpp:47:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < seg[id].size(); i++) koj[h][seg[id][i]] = i + 1;
                   ~~^~~~~~~~~~~~~~~~
street_lamps.cpp:58:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < seg[id].size(); i++) koj[h][seg[id][i]] = i + 1;
                  ~~^~~~~~~~~~~~~~~~
street_lamps.cpp: In function 'void Add(int, int, int, int, int, int, int)':
street_lamps.cpp:76:7: warning: unused variable 'zar' [-Wunused-variable]
   int zar = 1;
       ^~~

Subtask #1
0 / 20.0

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

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 347 ms 96504 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 39 ms 63992 KB Output is correct
2 Correct 40 ms 64128 KB Output is correct
3 Correct 39 ms 64128 KB Output is correct
4 Correct 42 ms 64120 KB Output is correct
5 Correct 790 ms 131632 KB Output is correct
6 Correct 1213 ms 156276 KB Output is correct
7 Correct 1481 ms 177920 KB Output is correct
8 Correct 1624 ms 205684 KB Output is correct
9 Correct 329 ms 98452 KB Output is correct
10 Correct 357 ms 102352 KB Output is correct
11 Correct 369 ms 103812 KB Output is correct
12 Correct 1550 ms 204048 KB Output is correct
13 Correct 1579 ms 204788 KB Output is correct

Subtask #4
0 / 20.0

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

Subtask #5
0 / 20.0

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