oj.uz

Submission #139510

# Submission time Handle Problem Language Result Execution time Memory
139510 2019-07-31T23:15:35 Z eriksuenderhauf Street Lamps (APIO19_street_lamps) C++11
40 / 100
 5000 ms 33928 KB 
#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;
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) {
			if (t == rhs.t) {
				if (a == rhs.a)
					return val < rhs.val;
				return a < rhs.a;
			}
			return t < rhs.t;
		}
		return b > rhs.b;
	}
};

map<sweep,int> cparr;
map<pii,int> act;

int f(int ind) {
	ind++;
	int ret = 0;
	while (ind) {
		ret += sm[ind];
		ind -= ind & -ind;
	}
	return ret;
}

void g(int ind, int v) {
	ind++;
	while (ind < MAXN) {
		sm[ind] += v;
		ind += ind & -ind;
	}
}

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() {
	clock_t tim = clock();
	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];
		g(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);
		}
	}
	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[{1, lo, ind-1, 0}] += 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[{1, ind+1, hi, 0}] += 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[{1, lo, hi, 0}] += 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[{2, qry[j].a, qry[j].b-1, j}] = 0;
			//int cur = sm[qry[j].b-1] - sm[qry[j].a-1];
			int cur = f(qry[j].b-1)-f(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 it: cparr) {
			sweep cur = it.fi;
			if (cur.t == 1)
				upd(1,n,1,cur.a,cur.b,it.se);
			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) {
				g(qry[j].a,(1^a[qry[j].a])-a[qry[j].a]);
				a[qry[j].a] ^= 1;
			} else {
				cparr.erase({2, qry[j].a, qry[j].b-1, j});
				printf("%d\n", ans[j]);
			}
	}
	//cerr << clock() - tim << "\n";;
	return 0;
}

Compilation message

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:80:10: warning: unused variable 'tim' [-Wunused-variable]
  clock_t tim = clock();
          ^~~
street_lamps.cpp:107:6: warning: unused variable 'curm' [-Wunused-variable]
  int curm = 0;
      ^~~~
street_lamps.cpp:82: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:83: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:89:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", tmp);
   ~~~~~^~~~~~~~~~~
street_lamps.cpp:92: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:95: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 380 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 380 KB Output is correct
4 Correct 3 ms 504 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 2467 ms 6372 KB Output is correct
2 Correct 2457 ms 6568 KB Output is correct
3 Correct 2829 ms 8584 KB Output is correct
4 Correct 4596 ms 28480 KB Output is correct
5 Execution timed out 5081 ms 27648 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 632 KB Output is correct
2 Correct 4 ms 504 KB Output is correct
3 Correct 5 ms 504 KB Output is correct
4 Correct 4 ms 504 KB Output is correct
5 Correct 2932 ms 33068 KB Output is correct
6 Correct 4998 ms 31760 KB Output is correct
7 Execution timed out 5103 ms 26400 KB Time limit exceeded
8 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 3 ms 544 KB Output is correct
5 Correct 2505 ms 20116 KB Output is correct
6 Correct 3660 ms 24852 KB Output is correct
7 Correct 3857 ms 29196 KB Output is correct
8 Correct 3380 ms 33928 KB Output is correct
9 Correct 715 ms 5260 KB Output is correct
10 Correct 238 ms 4472 KB Output is correct
11 Correct 712 ms 5108 KB Output is correct
12 Correct 236 ms 4476 KB Output is correct
13 Correct 707 ms 5160 KB Output is correct
14 Correct 235 ms 4488 KB Output is correct
15 Correct 2109 ms 14124 KB Output is correct
16 Correct 2084 ms 15536 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 380 KB Output is correct
4 Correct 3 ms 504 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 2467 ms 6372 KB Output is correct
9 Correct 2457 ms 6568 KB Output is correct
10 Correct 2829 ms 8584 KB Output is correct
11 Correct 4596 ms 28480 KB Output is correct
12 Execution timed out 5081 ms 27648 KB Time limit exceeded
13 Halted 0 ms 0 KB -