oj.uz

Submission #139495

# Submission time Handle Problem Language Result Execution time Memory
139495 2019-07-31T21:58:08 Z eriksuenderhauf Street Lamps (APIO19_street_lamps) C++11
40 / 100
 5000 ms 60704 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() {
	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]);
	}
	return 0;
}

Compilation message

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:129:7: warning: unused variable 'm' [-Wunused-variable]
   int m = 0;
       ^
street_lamps.cpp:86:6: warning: unused variable 'curm' [-Wunused-variable]
  int curm = 0;
      ^~~~
street_lamps.cpp:59: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:60: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:64:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", tmp);
   ~~~~~^~~~~~~~~~~
street_lamps.cpp:67: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:72: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 248 KB Output is correct
4 Correct 2 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 4408 ms 25944 KB Output is correct
2 Correct 4756 ms 29608 KB Output is correct
3 Correct 4790 ms 30200 KB Output is correct
4 Execution timed out 5024 ms 42824 KB Time limit exceeded
5 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 5 ms 504 KB Output is correct
3 Correct 6 ms 504 KB Output is correct
4 Correct 4 ms 516 KB Output is correct
5 Correct 3408 ms 56612 KB Output is correct
6 Execution timed out 5020 ms 50600 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 5 ms 504 KB Output is correct
3 Correct 5 ms 504 KB Output is correct
4 Correct 2 ms 380 KB Output is correct
5 Correct 1238 ms 26152 KB Output is correct
6 Correct 3204 ms 36496 KB Output is correct
7 Correct 4134 ms 46860 KB Output is correct
8 Correct 4406 ms 60704 KB Output is correct
9 Correct 2792 ms 36508 KB Output is correct
10 Correct 2343 ms 45048 KB Output is correct
11 Correct 2887 ms 36416 KB Output is correct
12 Correct 2833 ms 45128 KB Output is correct
13 Correct 2972 ms 36452 KB Output is correct
14 Correct 2542 ms 45160 KB Output is correct
15 Correct 859 ms 19884 KB Output is correct
16 Correct 2029 ms 21120 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 248 KB Output is correct
4 Correct 2 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 4408 ms 25944 KB Output is correct
9 Correct 4756 ms 29608 KB Output is correct
10 Correct 4790 ms 30200 KB Output is correct
11 Execution timed out 5024 ms 42824 KB Time limit exceeded
12 Halted 0 ms 0 KB -