oj.uz

Submission #139505

# Submission time Handle Problem Language Result Execution time Memory
139505 2019-07-31T22:59:04 Z eriksuenderhauf Street Lamps (APIO19_street_lamps) C++11
60 / 100
 5000 ms 36760 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 = 3800;
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;

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];
	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});
					cparr[{1, lo, ind-1, j-it->se+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});
					cparr[{1, ind+1, hi, j-it->se+1}] += 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});
				cparr[{1, lo, hi, j-it->se+1}] += 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});
			cparr[{2, qry[j].a, qry[j].b-1, j}] = 0;
			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 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)
				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:61:10: warning: unused variable 'tim' [-Wunused-variable]
  clock_t tim = clock();
          ^~~
street_lamps.cpp:86:6: warning: unused variable 'curm' [-Wunused-variable]
  int curm = 0;
      ^~~~
street_lamps.cpp:63: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:64: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:67:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", tmp);
   ~~~~~^~~~~~~~~~~
street_lamps.cpp:70: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:73: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
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2756 ms 10244 KB Output is correct
2 Correct 3444 ms 15292 KB Output is correct
3 Correct 3604 ms 16964 KB Output is correct
4 Correct 4742 ms 30208 KB Output is correct
5 Correct 4850 ms 28208 KB Output is correct
6 Correct 4226 ms 31596 KB Output is correct
7 Correct 1998 ms 15176 KB Output is correct
8 Correct 2004 ms 16504 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 480 KB Output is correct
3 Correct 5 ms 504 KB Output is correct
4 Correct 4 ms 504 KB Output is correct
5 Correct 2801 ms 33112 KB Output is correct
6 Execution timed out 5011 ms 31420 KB Time limit exceeded
7 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 512 KB Output is correct
3 Correct 5 ms 504 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 2354 ms 20232 KB Output is correct
6 Correct 3674 ms 24984 KB Output is correct
7 Correct 4090 ms 30328 KB Output is correct
8 Correct 3764 ms 36760 KB Output is correct
9 Correct 2251 ms 15384 KB Output is correct
10 Correct 485 ms 8568 KB Output is correct
11 Correct 2058 ms 16500 KB Output is correct
12 Correct 523 ms 8524 KB Output is correct
13 Correct 2001 ms 16452 KB Output is correct
14 Correct 475 ms 8312 KB Output is correct
15 Correct 2005 ms 15012 KB Output is correct
16 Correct 1994 ms 16356 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 2756 ms 10244 KB Output is correct
9 Correct 3444 ms 15292 KB Output is correct
10 Correct 3604 ms 16964 KB Output is correct
11 Correct 4742 ms 30208 KB Output is correct
12 Correct 4850 ms 28208 KB Output is correct
13 Correct 4226 ms 31596 KB Output is correct
14 Correct 1998 ms 15176 KB Output is correct
15 Correct 2004 ms 16504 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 4 ms 480 KB Output is correct
18 Correct 5 ms 504 KB Output is correct
19 Correct 4 ms 504 KB Output is correct
20 Correct 2801 ms 33112 KB Output is correct
21 Execution timed out 5011 ms 31420 KB Time limit exceeded
22 Halted 0 ms 0 KB -