The official APIO 2019 Problems and solutions in this post.

Problems :

Solution – A (Strange Device) :

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000005;
const int MAXT = 4200000;
using lint = long long;
using pi = pair<lint, lint>;

lint gcd(lint x, lint y){
	return y ? gcd(y, x%y) : x;
}

struct event{
	lint pos, st, ed;
	int dx;
	bool operator<(const event &e)const{
		return pos != e.pos ? pos < e.pos : dx > e.dx;
	}
};

struct strip{
	lint fuck, pos, dx;
	bool operator<(const strip &s)const{
		return pi(fuck, pos) < pi(s.fuck, s.pos);
	}
};

int n;
lint a, b, l[MAXN], r[MAXN];
map<lint, int> mp;
vector<strip> strips;

int main(){
	scanf("%d",&n);
	scanf("%lld %lld",&a,&b);
	for(int i=0; i<n; i++){
		scanf("%lld %lld",&l[i],&r[i]);
	}
	lint period = a / gcd(a, b + 1);
	for(int i=0; i<n; i++){
		vector<lint> v = {l[i] % b, 0, (r[i] + 1) % b};
		sort(v.begin(), v.end());
		v.resize(unique(v.begin(), v.end()) - v.begin());
		int ptr = 0;
		vector<event> tev;
		map<lint, int> dx;
		int cnt = 0;
		for(auto &j : v){
			ptr++;
			lint s = l[i] + b - j;
			lint e = r[i] + b - j;
			s = (s + b - 1) / b;
			e /= b;
			lint is = j;
			lint ie = (ptr < v.size() ? v[ptr] : b);
			if(e - s + 1 >= period){
				tev.push_back({is, 0, period, +1});
				tev.push_back({ie, 0, period, -1});
				dx[0]++;
				dx[period]--;
			}
			else if(s <= e){
				if(s % period > e % period){
					tev.push_back({is, s % period, period, +1});
					tev.push_back({ie, s % period, period, -1});
					tev.push_back({is, 0, e % period + 1, +1});
					tev.push_back({ie, 0, e % period + 1, -1});
					dx[s % period]++;
					dx[period]--;
					dx[0]++;
					dx[e % period + 1]--;
				}
				else{
					tev.push_back({is, s % period, e % period + 1, +1});
					tev.push_back({ie, s % period, e % period + 1, -1});
					dx[s % period]++;
					dx[e % period + 1]--;
				}
			}
			cnt++;
		}
		auto nitr = dx.begin();
		int tcnt = 0;
		for(auto &i : dx){
			nitr++;
			tcnt += i.second;
			if(nitr == dx.end()) break;
			if(tcnt == cnt){
				mp[i.first]++;
				mp[nitr->first]--;
			}
			else{
				for(auto &j : tev){
					lint st = max(i.first, j.st);
					lint ed = min(nitr->first, j.ed);
					for(lint jj = st; jj < ed; jj++){
						strips.push_back({jj, j.pos, j.dx});
					}
				}
			}
		}
	}
	auto nitr = mp.begin();
	int tcnt = 0;
	vector<lint> v;
	lint ret = 0;
	for(auto &i : mp){
		nitr++;
		tcnt += i.second;
		if(tcnt > 0 && nitr != mp.end()){
			ret += b * (nitr->first - i.first);
		}
		if(tcnt > 0){
			v.push_back(i.first);
			v.push_back(nitr->first);
		}
	}
	sort(strips.begin(), strips.end());
	for(int i=0; i<strips.size(); ){
		int e = i;
		while(e < strips.size() && strips[e].fuck == strips[i].fuck) e++;
		auto l = lower_bound(v.begin(), v.end(), strips[i].fuck + 1) - v.begin();
		if(l % 2 == 1){
			i = e;
			continue;
		}
		int cnt = 0;
		for(int j = i; j + 1 < e; j++){
			cnt += strips[j].dx;
			if(cnt > 0) ret += strips[j + 1].pos - strips[j].pos;
		}
		i = e;
	}
	cout << ret << endl;
}

SOLUTION – B (Bridges) :

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
const int B = 800;
using lint = long long;
using pi = pair<int, int>;

int n, m, q;
bool in_must[MAXN];
bool in_quer[MAXN];

struct disj{
	int pa[MAXN];
	int sz[MAXN];
	void init(int n){
		iota(pa, pa + n + 1, 0);
		fill(sz, sz + n + 1, 1);
	}
	int find(int x){
		return pa[x] == x ? x : find(pa[x]);
	}
	bool uni(int p, int q){
		p = find(p);
		q = find(q);
		if(p == q) return 0;
		if(sz[p] < sz[q]) swap(p, q);
		pa[q] = p;
		sz[p] += sz[q];
		return 1;
	}
	bool uni(int p, int q, vector<pi> &rvt){
		p = find(p);
		q = find(q);
		if(p == q) return 0;
		if(sz[p] < sz[q]) swap(p, q);
		rvt.emplace_back(q, -1);
		pa[q] = p;
		rvt.emplace_back(p, sz[p]);
		sz[p] += sz[q];
		return 1;
	}
	void revert(vector<pi> &v){
		reverse(v.begin(), v.end());
		for(auto &i : v){
			if(i.second == -1) pa[i.first] = i.first;
			else sz[i.first] = i.second;
		}
		v.clear();
	}
	int getSz(int x){ return sz[find(x)]; }
}disj;

struct edg{
	int s, e, x, idx;
	bool operator<(const edg &e)const{
		return x < e.x;
	}
}e[MAXN];

struct qry{
	int pos, idx, thres;
	bool operator<(const qry &q)const{
		return thres < q.thres;
	}
};

int t[MAXN], x[MAXN], y[MAXN];
int rev[MAXN], ret[MAXN];
int aux[MAXN];

int main(){
	scanf("%d %d",&n,&m);
	for(int i=0; i<m; i++){
		scanf("%d %d %d",&e[i].s,&e[i].e,&e[i].x);
		e[i].x = 1696969696 - e[i].x;
		e[i].idx = i + 1;
	}
	scanf("%d",&q);
	for(int i=0; i<q; i++){
		scanf("%d %d %d",&t[i],&x[i],&y[i]);
		y[i] = 1696969696 - y[i];
	}
	sort(e, e + m);
	for(int i=0; i<q; i+=B){
		for(int i=0; i<m; i++) rev[e[i].idx] = i;
		memset(in_must, 0, sizeof(in_must));
		vector<int> must;
		vector<int> maybe;
		disj.init(n);
		for(int j=i; j<i+B && j<q; j++){
			if(t[j] == 1){
				int pos = rev[x[j]];
				in_quer[pos] = 1;
			}
		}
		for(int i=0; i<m; i++){
			if(in_quer[i]) continue;
			if(disj.uni(e[i].s, e[i].e)){
				must.push_back(i);
			}
		}
		vector<qry> qr;
		vector<int> drog;
		for(int j=i; j<i+B && j<q; j++){
			if(t[j] == 2){
				qr.push_back({x[j], j, y[j]});
			}
			if(t[j] == 1){
				if(in_quer[rev[x[j]]]){
					in_quer[rev[x[j]]] = 0;
					drog.push_back(x[j]);
				}
			}
		}
		sort(qr.begin(), qr.end());
		disj.init(n);
		int ptr = 0;
		for(auto &k : qr){
			while(ptr < must.size() && e[must[ptr]].x <= k.thres){
				disj.uni(e[must[ptr]].s, e[must[ptr]].e);
				ptr++;
			}
			vector<pi> logs;
			for(int j=i; j<k.idx; j++){
				if(t[j] == 1){
					aux[x[j]] = y[j];
				}
			}
			for(auto &i : maybe){
				if(e[i].x <= k.thres){
					disj.uni(e[i].s, e[i].e, logs);
				}
			}
			for(auto &i : drog){
				int pos = rev[i];
				int cost = aux[i];
				if(cost == 0) cost = e[pos].x;
				if(cost <= k.thres){
					disj.uni(e[pos].s, e[pos].e, logs);
				}
			}
			ret[k.idx] = disj.getSz(k.pos);
			disj.revert(logs);
			for(int j=i; j<k.idx; j++){
				if(t[j] == 1){
					aux[x[j]] = 0;
				}
			}
		}
		for(int j=i; j<q && j<i+B; j++){
			if(t[j] == 1) aux[x[j]] = y[j];
		}
		vector<edg> l, r;
		for(int i=0; i<m; i++){
			if(aux[e[i].idx]){
				e[i].x = aux[e[i].idx];
				aux[e[i].idx] = 0;
				r.push_back(e[i]);
			}
			else l.push_back(e[i]);
		}
		sort(r.begin(), r.end());
		merge(l.begin(), l.end(), r.begin(), r.end(), e);
	}
	for(int i=0; i<q; i++) if(t[i] == 2) printf("%d\n", ret[i]);
}

SOLUTION – C (Street Lamps) :

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 300005;
using lint = long long;
using pi = pair<int, int>;

struct bit{
	int tree[MAXN];
	void add(int x, int v){
		while(x < MAXN){
			tree[x] += v;
			x += x & -x;
		}
	}
	int query(int x){
		int ret = 0;
		while(x){
			ret += tree[x];
			x -= x & -x;
		}
		return ret;
	}
}bit;

struct intv{
	int s, e, x;
	bool operator<(const intv &i)const{
		return s < i.s;
	}
};

struct event{
	int x, y, t, type;
	bool operator<(const event &e)const{
		return pi(x, y) < pi(e.x, e.y);
	}
};

int ret[MAXN];
vector<event> ev;
set<intv> s;

void add_rect(int s, int e, int x){
	ev.push_back({s, s, +x, 1});
	ev.push_back({s, e + 1, -x, 1});
	ev.push_back({e + 1, s, -x, 1});
	ev.push_back({e + 1, e + 1, +x, 1});
}

void solve(int s, int e){
	if(s == e) return;
	int m = (s+e)/2;
	solve(s, m);
	solve(m + 1, e);
	vector<event> pupd, quer;
	for(int i=s; i<=m; i++){
		if(ev[i].type == 1){
			pupd.push_back(ev[i]);
		}
	}
	for(int i=m+1; i<=e; i++){
		if(ev[i].type == 2){
			quer.push_back(ev[i]);
		}
	}
	sort(pupd.begin(), pupd.end());
	sort(quer.begin(), quer.end());
	int ptr = 0;
	for(auto &i : quer){
		while(ptr < pupd.size() && pupd[ptr].x <= i.x){
			bit.add(pupd[ptr].y, pupd[ptr].t);
			ptr++;
		}
		ret[i.t] += bit.query(i.y);
	}
	for(int i=0; i<ptr; i++){
		bit.add(pupd[i].y, -pupd[i].t);
	}
}

int n, q;
char str[MAXN];

int main(){
	scanf("%d %d",&n,&q);
	scanf("%s", str + 1);
	for(int i=1; i<=n; ){
		if(str[i] == '0'){
			i++;
			continue;
		}
		int e = i;
		while(e <= n && str[e] == '1') e++;
		s.insert({i, e - 1, 1});
		i = e;
	}
	char buf[10];
	for(int i=1; i<=q; i++){
		scanf("%s", buf);
		if(*buf == 't'){
			int t; scanf("%d",&t);
			if(str[t] == '0'){
				int st = t, ed = t;
				auto l = s.lower_bound({t + 1, -1, -1});
				if(l != s.end() && l->s == t + 1){
					add_rect(l->s, l->e, i + 1 - l->x);
					ed = l->e;
					l = s.erase(l);
				}
				if(l != s.begin() && prev(l)->e == t - 1){
					l--;
					add_rect(l->s, l->e, i + 1 - l->x);
					st = l->s;
					s.erase(l);
				}
				s.insert({st, ed, i + 1});
			}
			if(str[t] == '1'){
				auto l = --s.lower_bound({t + 1, -1, -1});
				add_rect(l->s, l->e, i + 1 - l->x);
				vector<intv> newV;
				if(l->s < t){
					newV.push_back({l->s, t - 1, i + 1});
				}
				if(t < l->e){
					newV.push_back({t + 1, l->e, i + 1});
				}
				s.erase(l);
				for(auto &i : newV) s.insert(i);
			}
			str[t] ^= 1;
			ret[i] = -1;
		}
		else{
			int a, b; scanf("%d %d",&a,&b);
			b--;
			ev.push_back({a, b, i, 2});
			auto l = s.lower_bound({a + 1, -1, -1});
			if(l != s.begin()){
				l--;
				if(l->s <= a && b <= l->e){
					ret[i] += i + 1 - l->x;
				}
			}
		}
	}
	solve(0, ev.size() - 1);
	for(int i=1; i<=q; i++){
		if(ret[i] >= 0) printf("%d\n", ret[i]);
	}
}

 561 total views,  2 views today