Submission #497297

#	Time	Username	Problem	Language	Result	Execution time	Memory
497297		maomao90	Street Lamps (APIO19_street_lamps)	C++17	0 / 100	766 ms	26332 KiB

street_lamps

// She will give birth to a son, and you are to give him the name Jesus,
// because he will save his people from their sins.
// Matthew 1:21
#include <bits/stdc++.h> 
using namespace std;

template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
#define REP(i, s, e) for (int i = s; i < e; i++)
#define RREP(i, s, e) for (int i = s; i >= e; i--)
typedef long long ll;
typedef long double ld;
#define MP make_pair
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
#define MT make_tuple
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;

#ifdef DEBUG
#define debug(args...) printf(args)
#else
#define debug(args...)
#endif

#define INF 1000000005
#define LINF 1000000000000000005
#define MOD 1000000007
#define MAXN 300005

struct upd {
	int x1, x2, y1, y2, v, isq;
	bool operator< (const upd& o) const {
		return x1 < o.x1;
	}
};

int n, q;
char s[MAXN];
set<ii> st;
upd upds[MAXN];
int ans[MAXN];
bool isq[MAXN];

struct rect {
	int x, s, e, v;
	bool operator< (const rect& o) const {
		return x < o.x;
	}
};

vector<rect> events;

int fw[MAXN];
void incre(int i, int v) {
	for (; i <= n + 2; i += i & -i) {
	   	fw[i] += v;
	}
}
inline void incre(int s, int e, int v) {
	incre(s, v); incre(e + 1, -v);
}
int qsm(int i) {
	int res = 0;
	for (; i > 0; i -= i & -i) {
		res += fw[i];
	}
	return res;
}

void dnc(int l, int r) {
	if (l >= r) return;
	int m = l + r >> 1;
	dnc(l, m); dnc(m + 1, r);
	debug("%d %d %d\n", l, r, m);
	REP (i, l, m + 1) {
		if (upds[i].isq) continue;
		debug("%d %d %d %d %d\n", upds[i].x1, upds[i].x2, upds[i].y1, upds[i].y2, upds[i].v);
		events.pb((rect) {upds[i].x1, upds[i].y1, upds[i].y2, upds[i].v});
		events.pb((rect) {upds[i].x2 + 1, upds[i].y1, upds[i].y2, -upds[i].v});
	}
	sort(ALL(events));
	sort(upds + m + 1, upds + r + 1);
	int ptr = 0;
	REP (i, m + 1, r + 1) {
		if (!upds[i].isq) continue;
		while (ptr < events.size() && events[ptr].x <= upds[i].x1) {
			debug(" %d to %d + %d\n", events[ptr].s, events[ptr].e, events[ptr].v);
			incre(events[ptr].s, events[ptr].e, events[ptr].v);
			ptr++;
		}
		debug("%d: + %d\n", upds[i].v, qsm(upds[i].y1));
		ans[upds[i].v] += qsm(upds[i].y1);
	}
	REP (i, 0, ptr) {
		incre(events[i].s, events[i].e, -events[i].v);
	}
	events.clear();
}

int main() {
	int _t = 1;
   	//scanf("%d", &_t);
	while (_t--) {
		scanf("%d%d", &n, &q);
		scanf(" %s", s + 1);
		s[0] = s[n + 1] = '0';
		int prv = 0;
		REP (i, 1, n + 2) {
			if (s[i] == '0' && s[i - 1] == '1') {
				debug("%d %d\n", prv + 1, i - 1);
				st.insert(MP(prv + 1, i - 1));
			}
			if (s[i] == '0') {
				prv = i;
			}
		}
		REP (i, 1, q + 1) {
			char t[10]; scanf(" %s", t);
			if (t[0] == 't') {
				int a; scanf("%d", &a);
				if (s[a] == '0') {
					s[a] = '1';
					auto it = st.insert(MP(a, a)).FI;
					if (it != st.begin() && prev(it) -> SE == a - 1) {
						auto prv = prev(it);
						ii nw = MP(prv -> FI, it -> SE);
						st.erase(prv);
						st.erase(it);
						it = st.insert(nw).FI;
					}
					auto nxt = next(it);
					if (nxt != st.end() && nxt -> FI == a + 1) {
						ii nw = MP(it -> FI, nxt -> SE);
						st.erase(nxt);
						st.erase(it);
						it = st.insert(nw).FI;
					}
					upds[i] = (upd) {it -> FI, a, a, it -> SE + 1, -i, 0};
				} else {
					s[a] = '0';
					auto it = st.upper_bound(MP(a, INF));
					assert(it != st.begin());
					it = prev(it);
					assert(it -> FI <= a && it -> SE >= a);
					if (it -> FI != a) {
						st.insert(MP(it -> FI, a - 1));
					}
					if (it -> SE != a) {
						st.insert(MP(a + 1, it -> SE));
					}
					upds[i] = (upd) {it -> FI, a, a, it -> SE + 1, i, 0};
					st.erase(it);
				}
			} else {
				isq[i] = 1;
				int a, b; scanf("%d%d", &a, &b);
				auto it = st.upper_bound(MP(a, INF));
				if (it != st.begin()) {
					it = prev(it);
				}
				if (it -> FI <= a && it -> SE >= b - 1) {
					debug("%d: +%d\n", i, i);
					ans[i] += i;
				}
				upds[i] = (upd) {a, -1, b, -1, i, 1};
			}
		}
		dnc(1, q);
		REP (i, 1, q + 1) {
			if (isq[i]) {
				debug("%d: ", i);
				printf("%d\n", ans[i]);
			}
		}
	}
	return 0;
}

/*
5 7
11011
query 1 2
query 1 2
query 1 6
query 3 4
toggle 3
query 3 4
query 1 6
*/

Compilation message (stderr)

street_lamps.cpp: In function 'void dnc(int, int)':
street_lamps.cpp:82:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   82 |  int m = l + r >> 1;
      |          ~~^~~
street_lamps.cpp:96:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<rect>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |   while (ptr < events.size() && events[ptr].x <= upds[i].x1) {
      |          ~~~~^~~~~~~~~~~~~~~
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:114:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |   scanf("%d%d", &n, &q);
      |   ~~~~~^~~~~~~~~~~~~~~~
street_lamps.cpp:115:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  115 |   scanf(" %s", s + 1);
      |   ~~~~~^~~~~~~~~~~~~~
street_lamps.cpp:128:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  128 |    char t[10]; scanf(" %s", t);
      |                ~~~~~^~~~~~~~~~
street_lamps.cpp:130:17: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  130 |     int a; scanf("%d", &a);
      |            ~~~~~^~~~~~~~~~
street_lamps.cpp:166:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  166 |     int a, b; scanf("%d%d", &a, &b);
      |               ~~~~~^~~~~~~~~~~~~~~~

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