Submission #561972

#	Time	Username	Problem	Language	Result	Execution time	Memory
561972		hhhhaura	Street Lamps (APIO19_street_lamps)	C++14	100 / 100	1029 ms	134208 KiB

street_lamps

#define wiwihorz
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse")
#pragma loop-opt(on)
#define rep(i, a, b) for(int i = a; i <= b; i ++)
#define rrep(i, a, b) for(int i = b; i >= a; i --)
#define all(x) x.begin(), x.end()
#define ceil(a, b) ((a + b - 1) / (b))
#define int long long int
#define lld long double
#define pii pair<int, int>
#define random mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count())
#define INF 1000000000000000000
#define MOD 1000000007
#define eps (1e-9)
using namespace std;
#ifdef wiwihorz
#define print(a...)cerr<<"Line "<<__LINE__<<":",kout("["+string(#a)+"] = ", a)
void vprint(auto L,auto R){while(L<R)cerr<<*L<<" \n"[next(L) == R], ++L; }
void kout() { cerr << endl; }
template<class T1,class ... T2>void kout(T1 a,T2 ... e){cerr<<a<<" ",kout(e...);}
#else
#define print(...) 0
#define vprint(...) 0
#endif
#define x first
#define y second
struct BIT {
	int n;
	vector<int> v;
	vector<pii> op;
	void init_(int _n) {
		n = _n;
		v.assign(n + 2, 0);
	}
	int lowbit(int x) {
		return x & (-x);
	}
	void modify(int x, int val, int yes) {
		if(!x) return;
		if(yes) op.push_back({x, val});
		for(int i = x; i <= n; i += lowbit(i)) {
			v[i] += val;
		}
	}
	int query(int x) {
		int ans = 0;
		if(x < 0) return 0;
		for(int i = x; i > 0; i -= lowbit(i)) {
			ans += v[i];
		}
		return ans;
	}
	void reset() {
		while(op.size()) {
			pii p = op.back();
			op.pop_back();
			modify(p.x, -p.y, 0);
		}
	}
};
namespace solver {
	int n, m;
	string s;
	struct pt { int t, x, y, tp; };
	vector<pt> op;
	set<int> v;
	vector<int> ans, vis, type;
	BIT bit;
	void init_(int _n, int _m, string _s) {
		n = _n, m = _m, s = _s;
		ans.assign(m + 1, 0);
		vis.assign(n + 1, 0);
		type.assign(m + 1, 0);
		bit.init_(n);
	}
	void CDQ(int l, int r) {
		int mid = (l + r) / 2;
		if(l == r) return;
		CDQ(l, mid);
		CDQ(mid + 1, r);
		int ii = l - 1;
		bit.reset();
		rep(i, mid + 1, r) if(op[i].tp == 0) {
			while(ii < mid && op[ii + 1].x >= op[i].x) {
				ii++;
				bit.modify(op[ii].y, op[ii].tp, 1);
			}
			int val = bit.query(n) - bit.query(op[i].y - 1);
			ans[op[i].t] += val;
		}
		vector<pt> tp(r - l + 1, {0, 0, 0, 0});
		merge(op.begin() + l, op.begin() + mid + 1, op.begin() + mid + 1, 
			op.begin() + r + 1, tp.begin(), [](pt a, pt b) { 
				if(a.x != b.x) return a.x > b.x;
				else if(a.y != b.y) return a.y > b.y;
				else return a.tp != 0;
		});
		rep(i, l, r) op[i] = tp[i - l];
		return;
	}
	void operate(int t, int l, int u, int r, int d, int val) {
		op.push_back({t, r, d, val});
		op.push_back({t, l - 1, d, -val});
		op.push_back({t, r, u - 1, -val});
		op.push_back({t, l - 1, u - 1, val});
	}
	void solve() {
		v.insert(0);
		v.insert(n + 1);
		rep(i, 0, n - 1) {
			vis[i + 1] = s[i] == '1';
			if(!vis[i + 1]) v.insert(i + 1);
		}
		rep(i, 1, m) {
			cin >> s;
			if(s == "toggle") {
				int x; cin >> x;
				v.insert(x);
				auto it = v.lower_bound(x);
				int l = *prev(it) + 1;
				int r = *next(it) - 1;
				vis[x] ^= 1;
				if(vis[x]) v.erase(v.find(x));
				int val = vis[x] ? -i : i;
				operate(i, l, x, x, r, val);
			}
			else {
				int l, r; 
				cin >> l >> r;
				op.push_back({i, l, r - 1, 0});
				auto it = v.lower_bound(l);
				if(*it >= r) ans[i] += i; 
				type[i] = 1;
			}
		}
		sort(all(op), [](pt a, pt b) {
			if(a.t != b.t) return a.t < b.t;
			else if(a.x != b.x) return a.x > b.x;
			else if(a.y != b.y) return a.y > b.y;
			else return a.tp != 0;
		});
		CDQ(0, signed(op.size()) - 1);
		rep(i, 1, m) if(type[i]) cout << ans[i] << "\n";
	}


};
using namespace solver;
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int n, m;
	cin >> n >> m;
	string s; cin >> s;
	init_(n, m, s);
	solve();
	return 0;
}

Compilation message (stderr)

street_lamps.cpp:5: warning: ignoring '#pragma loop ' [-Wunknown-pragmas]
    5 | #pragma loop-opt(on)
      | 
street_lamps.cpp:20:13: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   20 | void vprint(auto L,auto R){while(L<R)cerr<<*L<<" \n"[next(L) == R], ++L; }
      |             ^~~~
street_lamps.cpp:20:20: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   20 | void vprint(auto L,auto R){while(L<R)cerr<<*L<<" \n"[next(L) == R], ++L; }
      |                    ^~~~

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20