Submission #139551

#	Time	Username	Problem	Language	Result	Execution time	Memory
139551		eriksuenderhauf	Street Lamps (APIO19_street_lamps)	C++11	100 / 100	4211 ms	195860 KiB

street_lamps

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define pii pair<int, int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
const int INF = 1e9 + 7;
const int MAXN = 3e5 + 5;
char str[MAXN], tmp[20];
int a[MAXN], segcnt, root[MAXN], n, q;
int seg[MAXN*18*18], L[MAXN*18*18], R[MAXN*18*18];
struct query {
	int a, b, t;

	bool operator<(const query rhs) const {
		return a < rhs.a;
	}
};

set<query> act;

void upd(int l, int r, int& k, int x, int y, int v) {
	if (r < x || y < l || x > y) return;
	if (!k) k = ++segcnt;
	if (x <= l && r <= y) { seg[k] += v; return; }
	int m = (l+r) / 2;
	upd(l,m,L[k],x,y,v);
	upd(m+1,r,R[k],x,y,v);
}

int segqry(int l, int r, int k, int x) {
	if (l == r) return seg[k];
	int m = (l+r) / 2;
	return seg[k] + (x <= m ? segqry(l,m,L[k],x) : segqry(m+1,r,R[k],x));
}

void updF(int ind, int l, int r, int v) {
	while (ind < MAXN) {
		upd(1,MAXN,root[ind],l,r,v);
		ind += ind & -ind;
	}
}

int qryF(int ind, int idx) {
	int ret = 0;
	while (ind) {
		ret += segqry(1,MAXN,root[ind],idx);
		ind -= ind & -ind;
	}
	return ret;
}

int main() {
	clock_t tim = clock();
	scanf("%d %d", &n, &q);
	scanf("%s", str+1);
	for (int i = 1; i <= n; i++) a[i] = str[i]-'0';
	for (int i = 1, j = 1; i <= n+1; i = j + 1) {
		for (j = i; j <= n && a[j]; j++);
		act.insert({i,j,0});
	}
	for (int j = 1; j <= q; j++) {
		scanf("%s", tmp);
		if (tmp[0] == 't') {
			int idx;
			scanf("%d", &idx);
			if (a[idx]) {
				query cur = *prev(act.lower_bound({idx+1,0,0}));
				updF(cur.a, cur.a, cur.b, j-cur.t);
				updF(cur.b+1, cur.a, cur.b, -(j-cur.t));
				act.erase(cur);
				act.insert({cur.a,idx,j});
				act.insert({idx+1,cur.b,j});
			} else {
				query curL = *prev(act.lower_bound({idx+1,0,0}));
				query curR = *prev(act.lower_bound({idx+2,0,0}));
				updF(curL.a, curL.a, curL.b, j-curL.t);
				updF(curL.b+1, curL.a, curL.b, -(j-curL.t));
				updF(curR.a, curR.a, curR.b, j-curR.t);
				updF(curR.b+1, curR.a, curR.b, -(j-curR.t));
				act.erase(curL);
				act.erase(curR);
				act.insert({curL.a,curR.b,j});
			}
			a[idx] ^= 1;
		} else {
			int lo, hi;
			scanf("%d %d", &lo, &hi);
			int ans = qryF(lo, hi);
			query cur = *prev(act.lower_bound({lo+1,0,0}));
			if (hi <= cur.b)
				ans += j-cur.t;
			printf("%d\n",ans);
		}
	}
	//cerr << clock() - tim << "\n";;
	return 0;
}

Compilation message (stderr)

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:57:10: warning: unused variable 'tim' [-Wunused-variable]
  clock_t tim = clock();
          ^~~
street_lamps.cpp:58:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &q);
  ~~~~~^~~~~~~~~~~~~~~~~
street_lamps.cpp:59:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s", str+1);
  ~~~~~^~~~~~~~~~~~~
street_lamps.cpp:66:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", tmp);
   ~~~~~^~~~~~~~~~~
street_lamps.cpp:69:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &idx);
    ~~~~~^~~~~~~~~~~~
street_lamps.cpp:91:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d", &lo, &hi);
    ~~~~~^~~~~~~~~~~~~~~~~~~

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