oj.uz

Submission #979129

# Submission time Handle Problem Language Result Execution time Memory
979129 2024-05-10T09:29:45 Z c2zi6 Street Lamps (APIO19_street_lamps) C++14
60 / 100
 5000 ms 320812 KB 
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define replr(i, a, b) for (int i = int(a); i <= int(b); ++i)
#define reprl(i, a, b) for (int i = int(a); i >= int(b); --i)
#define rep(i, n) for (int i = 0; i < int(n); ++i)
#define mkp(a, b) make_pair(a, b)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VPI;
typedef vector<VI> VVI;
typedef vector<VVI> VVVI;
typedef vector<VPI> VVPI;
typedef pair<ll, ll> PLL;
typedef vector<ll> VL;
typedef vector<PLL> VPL;
typedef vector<VL> VVL;
typedef vector<VVL> VVVL;
typedef vector<VPL> VVPL;
template<class T> T setmax(T& a, T b) {if (a < b) return a = b; return a;}
template<class T> T setmin(T& a, T b) {if (a < b) return a; return a = b;}
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T>
using indset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

struct FENWICKTREE {
	VI a;
	VPI order;
	void init(int n) {
		a = VI(n);
		order.clear();
	}
	void add(int i, int s) {
		order.pb({i, s});
		while (i < a.size()) a[i] += s, i += i&-i;
	}
	int get(int i) {
		int ret = 0;
		while (i > 0) ret += a[i], i -= i&-i;
		return ret;
	}
	void clear() {
		while (order.size()) {
			auto[i, s] = order.back();
			order.pop_back();
			add(i, -s);
			order.pop_back();
		}
	}
} BIT;
struct POINT {
	int x, y, z, val, ind;
};
int n;
VI ret;
vector<POINT> v;
void CDQ(int l, int r) {
	if (l == r) return;
	int m = (l + r) / 2;
	CDQ(l, m), CDQ(m+1, r);
	vector<POINT> tmp;
	int i = l, j = m+1;
	while (i <= m && j <= r) {
		if (v[i].y <= v[j].y) BIT.add(v[i].z, v[i].val), tmp.pb(v[i++]);
		else ret[v[j].ind] += BIT.get(v[j].z-1), tmp.pb(v[j++]);
	}
	while (i <= m) BIT.add(v[i].z, v[i].val), tmp.pb(v[i++]);
	while (j <= r) ret[v[j].ind] += BIT.get(v[j].z-1), tmp.pb(v[j++]);
	replr(i, l, r) v[i] = tmp[i-l];
	BIT.clear();
}
void CDQ() {
	sort(all(v), [](POINT a, POINT b){
			return make_tuple(a.x, a.y, a.z) < make_tuple(b.x, b.y, b.z);
		});
	n = v.size();
	ret = VI(n+1);
	BIT.init(4e5);
	CDQ(0, n-1);
}
VI sol(vector<POINT> add, vector<POINT> get) {
	VI ans(get.size()+1);
	v.clear();
	rep(i, add.size()) v.pb(add[i]);
	rep(i, get.size()) v.pb(get[i]);
	CDQ();

	replr(i, 1, get.size()) ans[i] = ret[i] * get[i-1].z;
	rep(i, add.size()) add[i].val *= add[i].z;

	v.clear();
	rep(i, add.size()) v.pb(add[i]);
	rep(i, get.size()) v.pb(get[i]);
	CDQ();
	replr(i, 1, get.size()) ans[i] -= ret[i];
	return ans;
}

vector<POINT> avel;
vector<POINT> harc;
void add(int i, int j, int s, int t) {
	/* cout << i << " " << j << " " << s << endl; */
	avel.pb({i, i, t, s, 0});
	avel.pb({i, j+1, t, -s, 0});
	avel.pb({j+1, i, t, -s, 0});
	avel.pb({j+1, j+1, t, s, 0});
}

void solve() {
	/* int n; */
	/* cin >> n; */
	/* for (int tm = 1; tm <= n; tm++) { */
	/* 	string t; */
	/* 	cin >> t; */
	/* 	if (t == "ADD") { */
	/* 		int cnt; */
	/* 		cin >> cnt; */
	/* 		while (cnt--) { */
	/* 			int l, r, s; */
	/* 			cin >> l >> r >> s; */
	/* 			add(l, r, s, tm); */
	/* 		} */
	/* 	} else { */
	/* 		int l, r; */
	/* 		cin >> l >> r; */
	/* 		r--; */
	/* 		harc.pb({l, r, tm, 0, (int)harc.size()+1}); */
	/* 	} */
	/* } */

	int n, q;
	cin >> n >> q;
	VI a(n);
	rep(i, n) {
		char ch;
		cin >> ch;
		a[i] = (ch == '1');
	}
	auto fn = [&](int i){
		for (int j = i; j < n; j++) if (a[j] == 0) return j;
		return n;
	};
	auto ln = [&](int i){
		for (int j = i; j >= 0; j--) if (a[j] == 0) return j;
		return -1;
	};
	for (int i = 0; i < n; i++) if (a[i]) {
		int j = fn(i)-1;
		add(i+1, j+1, +1, 1);
		i = j;
	}

	rep(tm, q) {
		string t;
		cin >> t;
		if (t == "query") {
			int l, r;
			cin >> l >> r;
			harc.pb({l, r-1, tm+2, 0, (int)harc.size()+1});
		} else {
			int i;
			cin >> i;
			i--;
			if (a[i] == 0) {
				a[i] = 1;
				if (i < n-1 && a[i+1]) {
					add(i+2, fn(i+1), -1, tm+2);
				}
				if (i > 0 && a[i-1]) {
					add(ln(i-1)+2, i, -1, tm+2);
				}
				add(ln(i)+2, fn(i), +1, tm+2);
			} else if (a[i] == 1) {
				add(ln(i)+2, fn(i), -1, tm+2);
				a[i] = 0;
				if (i < n-1 && a[i+1]) {
					add(i+2, fn(i+1), +1, tm+2);
				}
				if (i > 0 && a[i-1]) {
					add(ln(i-1)+2, i, +1, tm+2);
				}
			}
		}
	}
	VI ans = sol(avel, harc);
	replr(i, 1, harc.size()) cout << ans[i] << " "; cout << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int t = 1;
    /* cin >> t; */
    while (t--) solve();
}

Compilation message

street_lamps.cpp: In member function 'void FENWICKTREE::add(int, int)':
street_lamps.cpp:42:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |   while (i < a.size()) a[i] += s, i += i&-i;
      |          ~~^~~~~~~~~~
street_lamps.cpp: In member function 'void FENWICKTREE::clear()':
street_lamps.cpp:51:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   51 |    auto[i, s] = order.back();
      |        ^
street_lamps.cpp: In function 'void solve()':
street_lamps.cpp:7:24: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
    7 | #define replr(i, a, b) for (int i = int(a); i <= int(b); ++i)
      |                        ^~~
street_lamps.cpp:193:2: note: in expansion of macro 'replr'
  193 |  replr(i, 1, harc.size()) cout << ans[i] << " "; cout << endl;
      |  ^~~~~
street_lamps.cpp:193:50: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  193 |  replr(i, 1, harc.size()) cout << ans[i] << " "; cout << endl;
      |                                                  ^~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3420 KB Output is correct
2 Correct 2 ms 3420 KB Output is correct
3 Correct 2 ms 3420 KB Output is correct
4 Correct 2 ms 3420 KB Output is correct
5 Correct 2 ms 3676 KB Output is correct
6 Correct 1 ms 3420 KB Output is correct
7 Correct 2 ms 3420 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2355 ms 175992 KB Output is correct
2 Correct 2395 ms 175396 KB Output is correct
3 Correct 2530 ms 173240 KB Output is correct
4 Correct 3232 ms 196280 KB Output is correct
5 Correct 3356 ms 203964 KB Output is correct
6 Correct 3526 ms 213192 KB Output is correct
7 Correct 624 ms 53016 KB Output is correct
8 Correct 585 ms 51476 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 4220 KB Output is correct
2 Correct 12 ms 4264 KB Output is correct
3 Correct 10 ms 4024 KB Output is correct
4 Correct 3 ms 3676 KB Output is correct
5 Correct 4358 ms 305748 KB Output is correct
6 Correct 4317 ms 297404 KB Output is correct
7 Correct 3225 ms 205184 KB Output is correct
8 Correct 637 ms 51836 KB Output is correct
9 Correct 418 ms 33600 KB Output is correct
10 Correct 412 ms 41908 KB Output is correct
11 Correct 449 ms 44184 KB Output is correct
12 Correct 617 ms 51104 KB Output is correct
13 Correct 627 ms 50432 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3672 KB Output is correct
2 Correct 7 ms 3840 KB Output is correct
3 Correct 12 ms 4232 KB Output is correct
4 Correct 15 ms 4324 KB Output is correct
5 Correct 1349 ms 90692 KB Output is correct
6 Correct 2451 ms 163360 KB Output is correct
7 Correct 3470 ms 212176 KB Output is correct
8 Execution timed out 5015 ms 320812 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3420 KB Output is correct
2 Correct 2 ms 3420 KB Output is correct
3 Correct 2 ms 3420 KB Output is correct
4 Correct 2 ms 3420 KB Output is correct
5 Correct 2 ms 3676 KB Output is correct
6 Correct 1 ms 3420 KB Output is correct
7 Correct 2 ms 3420 KB Output is correct
8 Correct 2355 ms 175992 KB Output is correct
9 Correct 2395 ms 175396 KB Output is correct
10 Correct 2530 ms 173240 KB Output is correct
11 Correct 3232 ms 196280 KB Output is correct
12 Correct 3356 ms 203964 KB Output is correct
13 Correct 3526 ms 213192 KB Output is correct
14 Correct 624 ms 53016 KB Output is correct
15 Correct 585 ms 51476 KB Output is correct
16 Correct 12 ms 4220 KB Output is correct
17 Correct 12 ms 4264 KB Output is correct
18 Correct 10 ms 4024 KB Output is correct
19 Correct 3 ms 3676 KB Output is correct
20 Correct 4358 ms 305748 KB Output is correct
21 Correct 4317 ms 297404 KB Output is correct
22 Correct 3225 ms 205184 KB Output is correct
23 Correct 637 ms 51836 KB Output is correct
24 Correct 418 ms 33600 KB Output is correct
25 Correct 412 ms 41908 KB Output is correct
26 Correct 449 ms 44184 KB Output is correct
27 Correct 617 ms 51104 KB Output is correct
28 Correct 627 ms 50432 KB Output is correct
29 Correct 4 ms 3672 KB Output is correct
30 Correct 7 ms 3840 KB Output is correct
31 Correct 12 ms 4232 KB Output is correct
32 Correct 15 ms 4324 KB Output is correct
33 Correct 1349 ms 90692 KB Output is correct
34 Correct 2451 ms 163360 KB Output is correct
35 Correct 3470 ms 212176 KB Output is correct
36 Execution timed out 5015 ms 320812 KB Time limit exceeded
37 Halted 0 ms 0 KB -