제출 #555699

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
555699		Zanite	가로등 (APIO19_street_lamps)	C++17	100 / 100	3894 ms	286604 KiB

street_lamps

// "I assure you that you guys won't make it to the top 4"
// - Tzaph, 21 December 2021

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#define ll long long
#define ld long double
#define si short int
#define i8 __int128
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pld pair<ld, ld>
#define psi pair<si, si>
#define pi8 pair<i8, i8>
#define pq priority_queue
#define fi first
#define se second

#define sqr(x) ((x)*(x))
#define pow2(x) (1ll << (x))
#define debug(x) cout << #x << " = " << (x) << '\n'
#define debugV(x, a) cout << #x << "[" << (a) << "] = " << (x[a]) << '\n'

#define yume using
#define wo namespace
#define kanaeyo std
#define nazotte __gnu_pbds

yume wo kanaeyo;
yume wo nazotte;

template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
 
template<typename T> void maddto(T &a, T b, T mod) {a += b; a %= mod;}
template<typename T> void msubto(T &a, T b, T mod) {a -= b; while (a < 0) a += mod; a %= mod;}
template<typename T> void mmulto(T &a, T b, T mod) {a *= b; a %= mod;}
 
template<typename T> T madd(T a, T b, T mod) {a += b; a %= mod; return a;}
template<typename T> T msub(T a, T b, T mod) {a -= b; while (a < 0) a += mod; return a;}
template<typename T> T mmul(T a, T b, T mod) {a *= b; a %= mod; return a;}

const ll ModA = 998244353;
const ll ModC = 1e9 + 7;
const ll INF = 1e18;
const ll iINF = 1e9;

const ld EPS = 1e-9;
const ld iEPS = 1e-6;

const int maxN = 3e5 + 5;

struct FenwickTree {
	ll sz;
	vector<ll> BIT;

	FenwickTree(ll _sz) {
		sz = _sz;
		BIT.assign(_sz+1, 0);
	}

	void update(ll idx, ll val) {
		for (; idx <= sz; idx += (idx & -idx)) {
			BIT[idx] += val;
		}
	}

	ll sum(ll idx) {
		ll ret = 0;
		idx = min(idx, sz);
		for (; idx > 0; idx -= (idx & -idx)) {
			ret += BIT[idx];
		}
		return ret;
 	}

	ll query(ll l, ll r) {
		return sum(r) - sum(l-1);
	}
};

struct FenwickTree2D {
	ll sz;
	vector<FenwickTree> inner;
	vector<vector<ll>> pos;

	FenwickTree2D(ll _sz) {
		sz = _sz;
		pos.assign(_sz + 1, vector<ll>(0));
	}

	void addPos(ll d1, ll d2) {
		for (; d1 <= sz; d1 += (d1 & -d1)) {
			pos[d1].push_back(d2);
		}
	}

	void build() {
		for (ll i = 0; i <= sz; i++) {
			sort(pos[i].begin(), pos[i].end());
			pos[i].erase(unique(pos[i].begin(), pos[i].end()), pos[i].end());

			inner.push_back(FenwickTree(pos[i].size()));
		}
	}

	void update(ll d1, ll d2, ll val) {
		for (; d1 <= sz; d1 += (d1 & -d1)) {
			ll d2_compressed = lower_bound(pos[d1].begin(), pos[d1].end(), d2) - pos[d1].begin() + 1;
			//cout << d1 << ' ' << d2 << ' ' << d2_compressed << '\n';
			inner[d1].update(d2_compressed, val);
		}
	}

	ll sum(ll d1, ll d2l, ll d2r) {
		ll ret = 0;
		for (; d1 > 0; d1 -= (d1 & -d1)) {
			ll d2l_compressed = lower_bound(pos[d1].begin(), pos[d1].end(), d2l) - pos[d1].begin() + 1;
			ll d2r_compressed = lower_bound(pos[d1].begin(), pos[d1].end(), d2r) - pos[d1].begin() + 1;
			//cout << d1 << ' ' << d2l_compressed << ' ' << d2r_compressed << '\n';
			ret += inner[d1].query(d2l_compressed, d2r_compressed);
		}
		return ret;
	}

	ll query(ll d1l, ll d1r, ll d2l, ll d2r) {
		//cout << sum(d1r, d2l, d2r) << ' ' << sum(d1l-1, d2l, d2r) << '\n';
		return sum(d1r, d2l, d2r) - sum(d1l-1, d2l, d2r);
	}

	void printPos() {
		for (ll i = 1; i <= sz; i++) {
			cout << i << ": ";
			for (auto j : pos[i]) {cout << j << " ";}
			cout << '\n';
		}
	}

	void print() {
		for (ll i = 1; i <= sz; i++) {
			cout << i << ": ";
			for (auto j : pos[i]) {
				cout << "{" << j << ": " << query(i, i, j, j) << "} ";
			}
			cout << '\n';
		}
	}
};

struct Operation {
	bool typ; // 0 = update, 1 = query
	ll x1, y1, x2, y2, t;
	pll val;

	Operation(ll _x1, ll _y1, pll _val) {
		typ = 0;
		x1 = _x1, y1 = _y1, val = _val;
	}

	Operation(ll _x1, ll _y1, ll _x2, ll _y2, ll _t) {
		typ = 1;
		x1 = _x1, y1 = _y1, x2 = _x2, y2 = _y2, t = _t;
	}
};

int n, q;
bool lamps[maxN];
set<pll> segments;
vector<Operation> op;

int main() {
	scanf("%d %d", &n, &q);

	char c;
	for (int i = 1; i <= n; i++) {
		scanf(" %c", &c);
		lamps[i] = (c == '1');
	}

	FenwickTree2D values = FenwickTree2D(n);
	FenwickTree2D toggled = FenwickTree2D(n);

	// NOTE: because we need <= operator in lower_bound,
	// all set elements are negative

	for (int start = -1, i = 1; i <= n+1; i++) {
		if (lamps[i]) {
			if (start == -1) {start = i;}
		} else {
			if (start != -1) {
				segments.insert({-start, -(i-1)});

				values.addPos(start, i-1);
				toggled.addPos(start, i-1);
				op.push_back(Operation(start, i-1, {q, 1}));

				start = -1;
			}
		}
	}

	char typ[10];
	for (int a, b, i = 1; i <= q; i++) {
		scanf(" %s", typ);
		if (typ[0] == 't') {
			scanf("%d", &a);
			if (lamps[a]) {
				// toggle the lamp off

				// remove segment of current lamp
				auto cseg_it = segments.lower_bound({-a, -iINF});
				pll cseg = *cseg_it;
				//cout << "cseg " << cseg.fi << ' ' << cseg.se << '\n';
				segments.erase(cseg);

				values.addPos(-cseg.fi, -cseg.se);
				toggled.addPos(-cseg.fi, -cseg.se);
				op.push_back(Operation(-cseg.fi, -cseg.se, {-(q-i), -1}));

				// insert new segments (except if it's of length 0)

				// left segment
				if (a != -cseg.fi) {
					segments.insert({cseg.fi, -(a-1)});

					values.addPos(-cseg.fi, a-1);
					toggled.addPos(-cseg.fi, a-1);
					op.push_back(Operation(-cseg.fi, a-1, {q-i, 1}));
				}
				// right segment
				if (a != -cseg.se) {
					segments.insert({-(a+1), cseg.se});

					values.addPos(a+1, -cseg.se);
					toggled.addPos(a+1, -cseg.se);
					op.push_back(Operation(a+1, -cseg.se, {q-i, 1}));
				}

			} else {
				// toggle the lamp on
				pll newseg = {-a, -a};

				// check if lamps next to it are on

				// left
				if (lamps[a-1]) {
					auto lseg_it = segments.lower_bound({-(a-1), -iINF});
					pll lseg = *lseg_it;
					newseg.fi = lseg.fi;
					segments.erase(lseg);

					values.addPos(-lseg.fi, -lseg.se);
					toggled.addPos(-lseg.fi, -lseg.se);
					op.push_back(Operation(-lseg.fi, -lseg.se, {-(q-i), -1}));
				}
				// right
				if (lamps[a+1]) {
					auto rseg_it = segments.lower_bound({-(a+1), -iINF});
					pll rseg = *rseg_it;
					newseg.se = rseg.se;
					segments.erase(rseg);

					values.addPos(-rseg.fi, -rseg.se);
					toggled.addPos(-rseg.fi, -rseg.se);
					op.push_back(Operation(-rseg.fi, -rseg.se, {-(q-i), -1}));
				}

				// insert new segment
				segments.insert(newseg);
				values.addPos(-newseg.fi, -newseg.se);
				toggled.addPos(-newseg.fi, -newseg.se);
				op.push_back(Operation(-newseg.fi, -newseg.se, {q-i, 1}));
			}

			lamps[a] = !lamps[a];

		} else {
			scanf("%d %d", &a, &b);

			op.push_back(Operation(1, b-1, a, n, i));
		}

		//for (auto i : segments) {cout << "{" << i.fi << ", " << i.se << "} ";}
		//cout << '\n';
		//D.print();
		//cout << '\n';
	}

	values.build();
	toggled.build();

	//values.printPos();
	//toggled.printPos();

	for (auto O : op) {
		if (O.typ == 0) {
			//printf("Update %lld %lld with %lld %lld\n", O.x1, O.y1, O.val.fi, O.val.se);
			values.update(O.x1, O.y1, O.val.fi);
			toggled.update(O.x1, O.y1, O.val.se);

			//values.print();
			//toggled.print();
		} else {
			//printf("Query (%lld %lld) to (%lld %lld) at time %lld\n", O.x1, O.y1, O.x2, O.y2, O.t);
			ll v = values.query(O.x1, O.x2, O.y1, O.y2);
			ll t = toggled.query(O.x1, O.x2, O.y1, O.y2);
			//printf("%lld %lld\n", v, t);
			ll fin = v - (1ll * t * (q-O.t));
			printf("%lld\n", fin);
		}
	}
}

컴파일 시 표준 에러 (stderr) 메시지

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:181:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  181 |  scanf("%d %d", &n, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~~
street_lamps.cpp:185:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  185 |   scanf(" %c", &c);
      |   ~~~~~^~~~~~~~~~~
street_lamps.cpp:213:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  213 |   scanf(" %s", typ);
      |   ~~~~~^~~~~~~~~~~~
street_lamps.cpp:215:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  215 |    scanf("%d", &a);
      |    ~~~~~^~~~~~~~~~
street_lamps.cpp:287:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  287 |    scanf("%d %d", &a, &b);
      |    ~~~~~^~~~~~~~~~~~~~~~~

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