oj.uz

Submission #139498

# Submission time Handle Problem Language Result Execution time Memory
139498 2019-07-31T22:04:09 Z eriksuenderhauf Street Lamps (APIO19_street_lamps) C++11
60 / 100
 5000 ms 36800 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) 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
				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:78:6: warning: unused variable 'curm' [-Wunused-variable]
  int curm = 0;
      ^~~~
street_lamps.cpp:55: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:56: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:59:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", tmp);
   ~~~~~^~~~~~~~~~~
street_lamps.cpp:62: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:65: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 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
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3384 ms 15508 KB Output is correct
2 Correct 3463 ms 15788 KB Output is correct
3 Correct 3931 ms 16088 KB Output is correct
4 Correct 4732 ms 29384 KB Output is correct
5 Correct 4891 ms 32632 KB Output is correct
6 Correct 3886 ms 35532 KB Output is correct
7 Correct 2049 ms 19816 KB Output is correct
8 Correct 2078 ms 21444 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 4 ms 504 KB Output is correct
3 Correct 6 ms 504 KB Output is correct
4 Correct 5 ms 504 KB Output is correct
5 Correct 2873 ms 33248 KB Output is correct
6 Correct 4867 ms 31836 KB Output is correct
7 Execution timed out 5083 ms 31236 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 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 504 KB Output is correct
5 Correct 2400 ms 20396 KB Output is correct
6 Correct 3477 ms 25276 KB Output is correct
7 Correct 3978 ms 30232 KB Output is correct
8 Correct 4000 ms 36800 KB Output is correct
9 Correct 2633 ms 18800 KB Output is correct
10 Correct 2005 ms 22972 KB Output is correct
11 Correct 2360 ms 18788 KB Output is correct
12 Correct 2134 ms 22904 KB Output is correct
13 Correct 2710 ms 18800 KB Output is correct
14 Correct 2017 ms 23032 KB Output is correct
15 Correct 2055 ms 14100 KB Output is correct
16 Correct 2066 ms 15608 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 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 3384 ms 15508 KB Output is correct
9 Correct 3463 ms 15788 KB Output is correct
10 Correct 3931 ms 16088 KB Output is correct
11 Correct 4732 ms 29384 KB Output is correct
12 Correct 4891 ms 32632 KB Output is correct
13 Correct 3886 ms 35532 KB Output is correct
14 Correct 2049 ms 19816 KB Output is correct
15 Correct 2078 ms 21444 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 4 ms 504 KB Output is correct
18 Correct 6 ms 504 KB Output is correct
19 Correct 5 ms 504 KB Output is correct
20 Correct 2873 ms 33248 KB Output is correct
21 Correct 4867 ms 31836 KB Output is correct
22 Execution timed out 5083 ms 31236 KB Time limit exceeded
23 Halted 0 ms 0 KB -