Submission #122519

#	Time	Username	Problem	Language	Result	Execution time	Memory
122519		abacaba	Street Lamps (APIO19_street_lamps)	C++14	100 / 100	1721 ms	200512 KiB

street_lamps

#include <bits/stdc++.h>
using namespace std;

const int N = 3e5 + 15;
int n, q, fenw[N], a[N];

struct node {
	node *l, *r;
	int val, add, pr, key;
	node() : val(0), add(0), pr(0), l(NULL), r(NULL) {}
	node(int key) : key(key), val(0), add(0), pr(0), l(NULL), r(NULL) {
		pr = (int)rand() * rand();
	}
};

struct query {
	int type, l, r;
} qs[N];

struct upd {
	int l, r, val;
	upd(int l, int r, int val) : l(l), r(r), val(val) {}
};

typedef node* pnode;

void push(pnode &t) {
	if(t) {
		if(t->l) {
			t->l->add += t->add;
			t->l->val += t->add;
		}
		if(t->r) {
			t->r->add += t->add;
			t->r->val += t->add;
		}
		t->add = 0;
	}
}

void split(pnode t, pnode &l, pnode &r, int key) {
	if(!t)
		return void(l = r = t);
	push(t);
	if(t->key <= key)
		split(t->r, t->r, r, key), l = t;
	else
		split(t->l, l, t->l, key), r = t;
}

void merge(pnode &t, pnode l, pnode r) {
	push(l);
	push(r);
	if(!l || !r)
		t = l ? l : r;
	else if(l->pr > r->pr)
		merge(l->r, l->r, r), t = l;
	else
		merge(r->l, l, r->l), t = r;
}

inline void inc(int i, int val) {
	for(; i <= n; i = (i | (i + 1)))
		fenw[i] += val;
}

inline int get(int i) {
	int res = 0;
	for(; i >= 1; i = (i & (i + 1)) - 1)
		res += fenw[i];
	return res;
}

inline int get(int l, int r) {
	if(l > r)
		return 0;
	return get(r) - get(l - 1);
}

void change(int i) {
	inc(i, -a[i]);
	a[i] ^= 1;
	inc(i, a[i]);
}

pnode t[N << 4];
vector <upd> add[N << 4];

int getleft(int j) {
	int l = 1, r = j, leftmost = j;
	while(l <= r) {
		int mid = l + r >> 1;
		if(j - mid == get(mid, j - 1)) {
			leftmost = mid;
			r = mid - 1;
		}
		else
			l = mid + 1;
	}
	return leftmost;
}

int getright(int j) {
	int l = j, r = n, rightmost = j;
	while(l <= r) {
		int mid = l + r >> 1;
		if(mid - j == get(j + 1, mid)) {
			rightmost = mid;
			l = mid + 1;
		}
		else
			r = mid - 1;
	}
	return rightmost;
}

void update(int v, int mostleft, int mostright, int val) {
	pnode t1, t23, t2, t3, cur;
	cur = t[v];
	split(cur, t1, t23, mostleft - 1);
	split(t23, t2, t3, mostright);
	if(t2) {
		t2->add += val;
		t2->val += val;
	}
	merge(t23, t2, t3);
	merge(cur, t1, t23);
}

void pusht(int v) {
	while(!add[v].empty()) {
		upd now = add[v].back();
		add[v << 1].push_back(now);
		add[v << 1 | 1].push_back(now);
		add[v].pop_back();
		update(v << 1, now.l, now.r, now.val);
		update(v << 1 | 1, now.l, now.r, now.val);
	}
}

void multiupdate(int v, int tl, int tr, int l, int r, int mostleft, int mostright, int val) {
	if(tl > r || tr < l || l > r)
		return;
	pusht(v);
	if(tl >= l && tr <= r) {
		add[v].push_back(*new upd(mostleft, mostright, val));
		update(v, mostleft, mostright, val);
		return;
	}
	int mid = tl + tr >> 1;
	multiupdate(v << 1, tl, mid, l, r, mostleft, mostright, val);
	multiupdate(v << 1 | 1, mid + 1, tr, l, r, mostleft, mostright, val);
}

void update(int v, int tl, int tr, int pos, pnode val) {
	if(tl == tr) {
		t[v] = val;
		return;
	}
	int mid = tl + tr >> 1;
	if(pos <= mid)
		update(v << 1, tl, mid, pos, val);
	else
		update(v << 1 | 1, mid + 1, tr, pos, val);
}

int get(int v, int tl, int tr, int l, int r) {
	pusht(v);
	if(tl == tr) {
		pnode t1, t23, t2, t3;
		split(t[v], t1, t23, l - 1);
		split(t23, t2, t3, l);
		int ans = 0;
		if(t2)
			ans = t2->val;
		merge(t23, t2, t3);
		merge(t[v], t1, t23);
		return ans;
	}
	int mid = tl + tr >> 1;
	if(r <= mid)
		return get(v << 1, tl, mid, l, r);
	return get(v << 1 | 1, mid + 1, tr, l, r);
}

set <int> rs[N], temporaryR;

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> q;
	for(int i = 1; i <= n; ++i) {
		char c;
		cin >> c;
		a[i] = (c == '1');
		inc(i, a[i]);
	}
	for(int i = 1; i <= q; ++i) {
		string s;
		cin >> s;
		qs[i].type = (s[0] != 't') + 1;
		if(qs[i].type == 1) {
			int j;
			cin >> j;
			qs[i].l = j;
		}
		else {
			cin >> qs[i].l >> qs[i].r;
			--qs[i].r;
			rs[qs[i].r].insert(qs[i].l);
			temporaryR.insert(qs[i].r);
		}
	}
	for(set <int>::iterator it = temporaryR.begin(); it != temporaryR.end(); ++it) {
		int r = *it;
		pnode t = NULL;
		for(set <int>::iterator ik = rs[r].begin(); ik != rs[r].end(); ++ik)
			merge(t, t, new node(*ik));
		update(1, 1, n, r, t);
	}
	for(int i = 1; i <= q; ++i) {
		if(qs[i].type == 1) {
			int j = qs[i].l;
			change(j);
			int leftmost = getleft(j);
			int rightmost = getright(j);
			if(!a[j])
				multiupdate(1, 1, n, j, rightmost, leftmost, j, i);
			else
				multiupdate(1, 1, n, j, rightmost, leftmost, j, -i);
		}
		else {
			int val = get(qs[i].l, qs[i].r);
			int ans = get(1, 1, n, qs[i].l, qs[i].r);
			if(val == qs[i].r - qs[i].l + 1)
				ans += i;
			cout << ans << endl;
		}
	}
	return 0;
}

Compilation message (stderr)

street_lamps.cpp: In constructor 'node::node()':
street_lamps.cpp:9:16: warning: 'node::pr' will be initialized after [-Wreorder]
  int val, add, pr, key;
                ^~
street_lamps.cpp:8:8: warning:   'node* node::l' [-Wreorder]
  node *l, *r;
        ^
street_lamps.cpp:10:2: warning:   when initialized here [-Wreorder]
  node() : val(0), add(0), pr(0), l(NULL), r(NULL) {}
  ^~~~
street_lamps.cpp: In constructor 'node::node(int)':
street_lamps.cpp:9:20: warning: 'node::key' will be initialized after [-Wreorder]
  int val, add, pr, key;
                    ^~~
street_lamps.cpp:9:6: warning:   'int node::val' [-Wreorder]
  int val, add, pr, key;
      ^~~
street_lamps.cpp:11:2: warning:   when initialized here [-Wreorder]
  node(int key) : key(key), val(0), add(0), pr(0), l(NULL), r(NULL) {
  ^~~~
street_lamps.cpp:9:16: warning: 'node::pr' will be initialized after [-Wreorder]
  int val, add, pr, key;
                ^~
street_lamps.cpp:8:8: warning:   'node* node::l' [-Wreorder]
  node *l, *r;
        ^
street_lamps.cpp:11:2: warning:   when initialized here [-Wreorder]
  node(int key) : key(key), val(0), add(0), pr(0), l(NULL), r(NULL) {
  ^~~~
street_lamps.cpp: In function 'int getleft(int)':
street_lamps.cpp:92:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid = l + r >> 1;
             ~~^~~
street_lamps.cpp: In function 'int getright(int)':
street_lamps.cpp:106:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid = l + r >> 1;
             ~~^~~
street_lamps.cpp: In function 'void multiupdate(int, int, int, int, int, int, int, int)':
street_lamps.cpp:150:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = tl + tr >> 1;
            ~~~^~~~
street_lamps.cpp: In function 'void update(int, int, int, int, pnode)':
street_lamps.cpp:160:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = tl + tr >> 1;
            ~~~^~~~
street_lamps.cpp: In function 'int get(int, int, int, int, int)':
street_lamps.cpp:180:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = tl + tr >> 1;
            ~~~^~~~

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20