Submission #139494

# Submission time Handle Problem Language Result Execution time Memory
139494 2019-07-31T21:57:22 Z eriksuenderhauf Street Lamps (APIO19_street_lamps) C++11
0 / 100
4347 ms 29456 KB
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define pii pair<int, int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
using namespace __gnu_pbds;
typedef cc_hash_table<int,null_type,hash<int>> ht;
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], nxu[MAXN];
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() {
	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];
	int p = 0;
	for (int j = 1; j <= q; j++) {
		scanf("%s", tmp);
		if (tmp[0] == 't') {
			qry[j].t = 1;
			scanf("%d", &qry[j].a);
			nxu[p] = j;
			p = j;
		} else {
			qry[j].t = 2;
			scanf("%d %d", &qry[j].a, &qry[j].b);
		}
	}
	nxu[p] = q;
	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;
		}
		int m = 0;
		multiset<sweep> arr = cparr;
		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;
			arr.insert({2, qry[j].a, qry[j].b-1, j});
			int cur = sm[qry[j].b-1] - sm[qry[j].a-1];
			int ind = j;
			if (cur == qry[j].b-qry[j].a)
				ind = i;
			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;
				}
				if (cur == qry[j].b-qry[j].a)
					ans[j]++;
			}
			for (auto j: x)
				a[j] ^= 1;
		}
		build(1,n,1);
		for (auto cur: arr) {
			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
				printf("%d\n", ans[j]);
	}
	cerr << clock() - tim << "\n";
	return 0;
}

Compilation message

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:130:7: warning: unused variable 'm' [-Wunused-variable]
   int m = 0;
       ^
street_lamps.cpp:87:6: warning: unused variable 'curm' [-Wunused-variable]
  int curm = 0;
      ^~~~
street_lamps.cpp:60: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:61: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:65:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", tmp);
   ~~~~~^~~~~~~~~~~
street_lamps.cpp:68: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);
    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 4347 ms 29456 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -