oj.uz

Submission #139499

# Submission time Handle Problem Language Result Execution time Memory
139499 2019-07-31T22:05:55 Z eriksuenderhauf Street Lamps (APIO19_street_lamps) C++11
40 / 100
 5000 ms 36568 KB 
#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;
const int BLOCK = 4000;
char str[MAXN], tmp[20];
int sm[MAXN], a[MAXN], ans[MAXN];
int nx[MAXN], val[MAXN];
int seg[MAXN*4];
struct query {
	int t, a, b;
} qry[MAXN];

struct sweep {
	int t, a, b, val;

	bool operator<(const sweep rhs) const {
		if (rhs.b == b) return t < rhs.t;
		return b > rhs.b;
	}
};

multiset<sweep> cparr;

void build(int l, int r, int k) {
	seg[k] = 0;
	if (l == r) return;
	int m = (l+r) / 2;
	build(l,m,k*2);
	build(m+1,r,k*2+1);
}

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

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

int main() {
	sm[0] = 0;
	int n, q; scanf("%d %d", &n, &q);
	scanf("%s", str+1);
	for (int i = 1; i <= n; i++) a[i] = str[i]-'0', val[i] = a[i];
	for (int j = 1; j <= q; j++) {
		scanf("%s", tmp);
		if (tmp[0] == 't') {
			qry[j].t = 1;
			scanf("%d", &qry[j].a);
		} else {
			qry[j].t = 2;
			scanf("%d %d", &qry[j].a, &qry[j].b);
		}
	}
	map<pii,int> act;
	for (int j = 1; j <= n; j++) {
		if (a[j] == 0) continue;
		int k = j;
		for (; k <= n && a[k] == 1; k++);
		act[mp(j,k-1)] = 1;
		nx[j] = k-1;
		nx[k-1] = j;
		j = k-1;
	}
	int curm = 0;
	for (int i = 1; i <= q; i += BLOCK) {
		for (int j = max(1,i-BLOCK); j < i; j++) {
			if (qry[j].t == 2) continue;
			int ind = qry[j].a;
			if (!val[ind]) {
				int lo = ind, hi = ind;
				if (val[ind-1]) {
					lo = nx[ind-1];
					auto it = act.find(mp(lo,ind-1));
					cparr.insert({1, lo, ind-1, j-it->se+1});
					act.erase(it);
					nx[ind-1] = 0;
				}
				if (val[ind+1]) {
					hi = nx[ind+1];
					auto it = act.find(mp(ind+1,hi));  
					cparr.insert({1, ind+1, hi, j-it->se+1});
					act.erase(it);
					nx[ind+1] = 0;
				}
				act[mp(lo,hi)] = j+1;
				nx[lo] = hi;
				nx[hi] = lo;
			} else {
				auto it = prev(act.upper_bound(mp(ind,INF)));
				int lo = it->fi.fi, hi = it->fi.se;
				cparr.insert({1, lo, hi, j-it->se+1});
				act.erase(it);
				nx[lo] = nx[hi] = 0;
				if (lo < ind) {
					act[mp(lo,ind-1)] = j+1;
					nx[lo] = ind-1;
					nx[ind-1] = lo;
				}
				if (ind < hi) {
					act[mp(ind+1,hi)] = j+1;
					nx[ind+1] = hi;
					nx[hi] = ind+1;
				}
			}
			val[ind] ^= 1;
		}
		for (int j = 1; j <= n; j++) sm[j] = sm[j-1] + a[j];
		for (int j = i; j <= min(q,i+BLOCK-1); j++) {
			if (qry[j].t == 1) continue;
			cparr.insert({2, qry[j].a, qry[j].b-1, j});
			int cur = sm[qry[j].b-1] - sm[qry[j].a-1];
			int ind = cur == qry[j].b-qry[j].a ? i : j;
			if (!act.empty()) {
				auto it = act.upper_bound(mp(qry[j].a,INF));
				if (it != act.begin()) {
					it = prev(it);
					if (it->fi.fi <= qry[j].a && qry[j].b-1 <= it->fi.se)
						ans[j] += ind-it->se+1;
				}
			}
			vector<int> x;
			for (int k = i; k < j; k++) {
				if (qry[k].t == 1 && qry[j].a <= qry[k].a && qry[k].a < qry[j].b) {
					x.pb(qry[k].a);
					a[qry[k].a] ^= 1;
					cur += 2*a[qry[k].a]-1;
				}
				ans[j] += (int)(cur == qry[j].b-qry[j].a);
			}
			for (auto j: x) a[j] ^= 1;
		}
		build(1,n,1);
		for (auto cur: cparr) {
			if (cur.t == 1)
				upd(1,n,1,cur.a,cur.b,cur.val);
			else
				ans[cur.val] += segqry(1,n,1,cur.a);
		}
		for (int j = i; j <= min(q,i+BLOCK-1); j++)
			if (qry[j].t == 1)
				a[qry[j].a] ^= 1;
			else {
				cparr.erase({2, qry[j].a, qry[j].b-1, j});
				printf("%d\n", ans[j]);
			}
	}
	return 0;
}

Compilation message

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:76:6: warning: unused variable 'curm' [-Wunused-variable]
  int curm = 0;
      ^~~~
street_lamps.cpp:53:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int n, q; scanf("%d %d", &n, &q);
            ~~~~~^~~~~~~~~~~~~~~~~
street_lamps.cpp:54: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:57:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", tmp);
   ~~~~~^~~~~~~~~~~
street_lamps.cpp:60:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &qry[j].a);
    ~~~~~^~~~~~~~~~~~~~~~~
street_lamps.cpp:63:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d", &qry[j].a, &qry[j].b);
    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

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

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3572 ms 15628 KB Output is correct
2 Correct 3561 ms 15668 KB Output is correct
3 Correct 3746 ms 15812 KB Output is correct
4 Correct 4628 ms 29220 KB Output is correct
5 Execution timed out 5087 ms 27476 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 4 ms 376 KB Output is correct
3 Correct 6 ms 504 KB Output is correct
4 Correct 5 ms 504 KB Output is correct
5 Correct 3055 ms 33092 KB Output is correct
6 Execution timed out 5035 ms 31536 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 504 KB Output is correct
2 Correct 6 ms 504 KB Output is correct
3 Correct 5 ms 504 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2501 ms 20092 KB Output is correct
6 Correct 3740 ms 25208 KB Output is correct
7 Correct 4208 ms 30244 KB Output is correct
8 Correct 3962 ms 36568 KB Output is correct
9 Correct 2597 ms 18660 KB Output is correct
10 Correct 2045 ms 22904 KB Output is correct
11 Correct 2472 ms 18732 KB Output is correct
12 Correct 1821 ms 22776 KB Output is correct
13 Correct 2387 ms 18748 KB Output is correct
14 Correct 1855 ms 22764 KB Output is correct
15 Correct 2098 ms 13964 KB Output is correct
16 Correct 2107 ms 15684 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 3572 ms 15628 KB Output is correct
9 Correct 3561 ms 15668 KB Output is correct
10 Correct 3746 ms 15812 KB Output is correct
11 Correct 4628 ms 29220 KB Output is correct
12 Execution timed out 5087 ms 27476 KB Time limit exceeded
13 Halted 0 ms 0 KB -