APIO 2019 Problems and Solutions

APIO 2019 Problems and Solutions

The official APIO 2019 Problems and solutions in this post.

Problems :

English

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]);
	}
}

 241 total views,  4 views today

Post Disclaimer

The hole problem statement are given by  apio2019.ru but the solution are generated by the sltechnicalacademy authority if any of the query regarding this post or website fill the following contact form thank you. 

Leave a Reply

Your email address will not be published. Required fields are marked *