oj.uz

Submission #255211

# Submission time Handle Problem Language Result Execution time Memory
255211 2020-07-31T14:34:16 Z Atalasion Street Lamps (APIO19_street_lamps) C++14
20 / 100
 1665 ms 199800 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);
		for (int i = 0; i < seg[id].size(); i++) koj[h][seg[id][i]] = i + 1;
  		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;
}

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][md]] < 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:45: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:55: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:69: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 63736 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 381 ms 93688 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 39 ms 64000 KB Output is correct
3 Correct 40 ms 64128 KB Output is correct
4 Correct 41 ms 64136 KB Output is correct
5 Correct 785 ms 127404 KB Output is correct
6 Correct 1248 ms 151540 KB Output is correct
7 Correct 1472 ms 172668 KB Output is correct
8 Correct 1600 ms 199800 KB Output is correct
9 Correct 320 ms 95764 KB Output is correct
10 Correct 346 ms 99344 KB Output is correct
11 Correct 354 ms 100740 KB Output is correct
12 Correct 1665 ms 198060 KB Output is correct
13 Correct 1646 ms 198860 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 64248 KB Output is correct
2 Incorrect 49 ms 64124 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 63736 KB Output isn't correct
2 Halted 0 ms 0 KB -