The official APIO 2019 Problems and solutions in this post.
Problems :
EnglishSolution – 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]);
}
}
1,261 total views, 3 views today