Believe or not, I was actually aiming for daily uploads.
The Siruseri Convention Centre
APIO 2009 #2
In this problem you are given multiple companies and their required start time and end time to use the auditorium. Then, you must figure out the maximum number of companies that can use the auditorium, and print a solution.
Until here, this problem is just a greedy problem. However in this problem, if there are multiple solutions, you have to print the lexicographically smallest solution. This makes the problem a lot harder.
We can easily find the maximum number of possible of companies. So we only have to find the lexicographically smallest solution. One way we could do this is try inserting each company into the solution in order, then check if we can earn the maximum solution.
Lets say we know the solution to the problem for companies $[1,N]$. If we insert a company with range $[s,e]$, we can know if the insertion is valid by checking if the solution for $[1,N]$ is equal to $[1,s-1] + 1 + [e+1,N]$. Since there are $N$ companies, we must now figure out a way to find the solution in a certain range quickly.
Lets define $R(i) = min(j>i|e_i < s_j)$ where $i, j$ are companies ads $s, e$ are start and end times. Then, a simple solution to the problem would be $[1, R(1), R(R(1)), \cdots]$. This solution can be used to find a solution for any range by changing the starting point.
Now, to find that solution in $O(NlogN)$, we can create a sparse table where $dp_{i,j}$ is the $R^{2^j}(i)$. This way, we can use the sparse table to find the last possible company in $O(NlogN)$ time and finding the solution in a certain range quickly, thus solving the problem.
code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<double,double> pdd;
//typedef complex<double> cpx;
#define fastio cin.tie(0)->sync_with_stdio(0); cout.tie(0);
#define all(x) x.begin(),x.end()
#define compress(x) x.erase(unique(all(x)),x.end())
#define ff first
#define ss second
#define INF 1e17
#define MAX 500010
#define SIZE 100010
#define MOD 1000000007
ll n,dp[200010][18];
pll a[200010];
vector<pll> v,fi;
ll cmp(pll a, pll b){
if(a.ss!=b.ss) return a.ss<b.ss;
return a.ff>b.ff;
}
ll solve(ll l, ll r){
if(l>r) return 0;
pll tmp = {l,-1LL};
ll pos = (*lower_bound(all(fi),tmp)).ss, ret = 1;
if(pos==n||v[pos].ss>r) return 0;
for(int i=17;i>=0;i--){
if(dp[pos][i]!=n&&v[dp[pos][i]].ss<=r){
ret += (1LL<<i);
pos = dp[pos][i];
}
}
return ret;
}
int main(){
fastio;
cin >> n;
for(int i=0;i<n;i++){
cin >> a[i].ff >> a[i].ss;
v.push_back(a[i]);
}
sort(all(v),cmp);
for(int i=0;i<n;i++){
if(!fi.empty()&&fi.back().ff>=v[i].ff) continue;
fi.push_back({v[i].ff,i});
}
fi.push_back({2e9+1LL,n});
ll cur = 0;
for(int i=0;i<n;i++){
while(cur<n&&v[i].ss>=v[cur].ff) cur++;
dp[i][0] = cur;
}
dp[n][0] = n;
for(int i=1;i<18;i++){
dp[n][i] = n;
for(int j=n-1;j>=0;j--){
dp[j][i] = dp[dp[j][i-1]][i-1];
}
}
set<pll> s;
vector<ll> ans;
s.insert({-1LL,2e9+1LL});
for(int i=0;i<n;i++){
auto it = s.upper_bound({a[i].ff,1e9+1LL}); it--;
pll iv = *it;
if(iv.ss<a[i].ss) continue;
ll t1 = solve(iv.ff,iv.ss);
ll t2 = solve(iv.ff,a[i].ff-1) + 1 + solve(a[i].ss+1,iv.ss);
if(t1!=t2) continue;
s.erase(it);
if(iv.ff<a[i].ff){
s.insert({iv.ff,a[i].ff-1});
}
if(a[i].ss<iv.ss){
s.insert({a[i].ss+1,iv.ss});
}
ans.push_back(i);
}
cout << ans.size() << "\n";
for(auto i:ans){
cout << i+1 << " ";
}
}
JOIG Tour
JOIG 2021/2022 Spring Training Camp #1-2
In this problem you are given the locations of multiple J, O, I, and G’s on a line and a start point and an end point. Then, you must find the shortest path that starts from the start point, passes a J, O, I, G in order(doesn’t mater if you pass some other alphabet in the middle) and goes to the end point.
If you think about it, from each point, there’s only two points that you have to consider as the next point. The closest point on the left, and the closest point on the right that has the desired alphabet, since you’re going to pass one of them whatever point you pick.
This means there are at most two points possible two go next, making a total of $2^4 = 16$ total paths to consider. Therefore, you just have to brute force all 16 paths and find the shortest one.
code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<double,double> pdd;
//typedef complex<double> cpx;
#define fastio cin.tie(0)->sync_with_stdio(0); cout.tie(0);
#define all(x) x.begin(),x.end()
#define compress(x) x.erase(unique(all(x)),x.end())
#define ff first
#define ss second
#define INF 1e17
#define MAX 500010
#define SIZE 100010
#define MOD 1000000007
ll n,q,s,t;
vector<ll> v[10];
ll solve(ll pos, ll num){
if(num==5){
return abs(pos-t);
}
ll idx1 = lower_bound(all(v[num]),pos) - v[num].begin();
ll idx2 = upper_bound(all(v[num]),pos) - v[num].begin();
idx1--; idx2--;
if(idx1==idx2) idx2++;
//cout << v[num][idx1] << " " << v[num][idx2] << " " << num << " " << pos << "\n";
ll d1 = LLONG_MAX, d2 = LLONG_MAX;
if(0<=idx1&&idx1<=n) d1 = min(d1,abs(pos-v[num][idx1])+solve(v[num][idx1],num+1));
if(0<=idx2&&idx2<=n) d2 = min(d2,abs(pos-v[num][idx2])+solve(v[num][idx2],num+1));
return min(d1,d2);
}
int main(){
fastio;
cin >> n;
for(int i=0;i<n;i++){
ll x; cin >> x;
char c; cin >> c;
if(c=='J') v[1].push_back(x);
else if(c=='O') v[2].push_back(x);
else if(c=='I') v[3].push_back(x);
else if(c=='G') v[4].push_back(x);
}
for(int i=1;i<=4;i++){
sort(all(v[i]));
}
cin >> q;
while(q--){
cin >> s >> t;
cout << solve(s,1) << "\n";
}
}
Meteor Shower
Daejeon Nationalwide Internet Competition 2016 #E
In this problem, you are given some polygons, and must count the number of polygons that cannot be seen from point (0,0).
The solution to this problem is quite easy. First, the upper part of every polygon is not needed, so we only keep track of the lower part of every polygon. Then we sort all the points that are in the lower parts in order of angle. Then we sweep each point, inserting and erasing the polygons in a set, while keeping track of which polygon is in front of the other. This can be done by doing a ccw check between the points on the polygon.
The solution is simple, but since this is a geometry problem, the implementation can be kind of difficult.
code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<double,double> pdd;
//typedef complex<double> cpx;
#define fastio cin.tie(0)->sync_with_stdio(0); cout.tie(0);
#define all(x) x.begin(),x.end()
#define compress(x) x.erase(unique(all(x)),x.end())
#define ff first
#define ss second
#define INF 1e17
#define MAX 500010
#define SIZE 100010
#define MOD 1000000007
struct P{
ll x, y;
bool operator < (const P &p) const {
ll k = x*p.y-y*p.x;
return k>0;
}
bool operator == (const P &p) const {
ll k = x*p.y-y*p.x;
return k==0;
}
};
ll ccw(P a, P b, P c){
ll k = (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
return (k>0)-(k<0);
}
ll n,cur,vis[1000100];
P O = {0,0};
vector<P> low[1000100];
vector<ll> lowr[1000100],in[1000100],out[1000100];
struct lhull{
ll x;
bool operator < (const lhull &l) const {
ll id1 = upper_bound(all(lowr[x]),cur)-lowr[x].begin();
ll id2 = upper_bound(all(lowr[l.x]),cur)-lowr[l.x].begin();
P p1 = low[x][id1-1], p2 = low[x][id1], q1 = low[l.x][id2-1], q2 = low[l.x][id2];
if(lowr[x][id1-1]<=lowr[l.x][id2-1]) return ccw(p1,p2,q1)<0;
else return ccw(q1,q2,p1)>0;
}
};
int main(){
fastio;
cin >> n;
for(int i=0;i<n;i++){
vector<P> v;
ll m; cin >> m;
for(int j=0;j<m;j++){
ll x,y; cin >> x >> y;
v.push_back({x,y});
}
ll s = 0, e = 0;
for(int j=0;j<m;j++){
if(ccw(O,v[j],v[s])>0||(ccw(O,v[j],v[s])==0&&v[s].y>v[j].y)) s = j;
if(ccw(O,v[j],v[e])<0||(ccw(O,v[j],v[s])==0&&v[s].y>v[j].y)) e = j;
}
for(int j = s;;j = (j+1)%m){
low[i].push_back(v[j]);
if(j==e) break;
}
}
vector<P> tmp;
for(int i=0;i<n;i++){
for(auto j:low[i]) tmp.push_back(j);
}
sort(all(tmp)); compress(tmp);
for(int i=0;i<n;i++){
for(auto j:low[i]){
lowr[i].push_back(lower_bound(all(tmp),j)-tmp.begin()+1);
}
in[lowr[i][0]].push_back(i);
out[lowr[i].back()].push_back(i);
}
set<lhull> s;
for(int i=1;i<=(ll)tmp.size();i++){
for(auto j:out[i]){
s.erase({j});
}
cur = i;
for(auto j:in[i]){
s.insert({j});
}
if(!s.empty()) vis[(*s.begin()).x] = 1;
}
ll ans = 0;
for(int i=0;i<n;i++){
if(!vis[i]) ans++;
}
cout << ans;
}
Switch the Lamp On
Baltic Olympiad in Informatics 2011 #3
In this problem, you can change the direction of wires, and you must find the minimum number of wires to change to connects the lamps.
This problem can be thought of as moving between diagonal points, with either weights 0 or 1, depending on the wires direction. Therefore the problem can be solved with 0-1 bfs.
code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<double,double> pdd;
//typedef complex<double> cpx;
#define fastio cin.tie(0)->sync_with_stdio(0); cout.tie(0);
#define all(x) x.begin(),x.end()
#define compress(x) x.erase(unique(all(x)),x.end())
#define ff first
#define ss second
#define INF 1e17
#define MAX 500010
#define SIZE 100010
#define MOD 1000000007
const ll dx[] = {-1,1,-1,1};
const ll dy[] = {-1,1,1,-1};
ll n,m,dist[510][510];
string s[510];
ll bfs(){
deque<pair<pll,ll> > dq;
for(int i=0;i<=n;i++){
for(int j=0;j<=m;j++){
dist[i][j] = 1e15+1LL;
}
}
dq.push_back({ {0,0},0});
dist[0][0] = 0;
while(!dq.empty()){
ll cx = dq.front().ff.ff, cy = dq.front().ff.ss;
ll d = dq.front().ss;
dq.pop_front();
//if(dist[cx][cy]<d) continue;
for(int i=0;i<4;i++){
ll nx = cx+dx[i], ny = cy+dy[i], nd = d;
if(nx<0||ny<0||nx>n||ny>m) continue;
ll lx, ly;
if(i==0){
lx = cx-1; ly = cy-1;
if(s[lx][ly]!='\\') nd++;
}
else if(i==1){
lx = cx; ly = cy;
if(s[lx][ly]!='\\') nd++;
}
else if(i==2){
lx = cx-1; ly = cy;
if(s[lx][ly]!='/') nd++;
}
else{
lx = cx; ly = cy-1;
if(s[lx][ly]!='/') nd++;
}
if(dist[nx][ny]>nd){
dist[nx][ny] = nd;
if(nd>d) dq.push_back({ {nx,ny},nd});
else dq.push_front({ {nx,ny},nd});
}
}
}
return dist[n][m];
}
int main(){
fastio;
cin >> n >> m;
for(int i=0;i<n;i++){
cin >> s[i];
}
ll k = bfs();
if(k>1e10) cout << "NO SOLUTION";
else cout << k;
}
本棚 (Bookshelf)
JOI 2010/2011 Spring Training Camp #4-2
In this problem, you are given the weights and the order of books. You can take a book out, slide the remaining books, then put the taken book back in. It takes as much energy as the books weight when taking out and putting a book back in. You have to find the minimum required strength to rearrange the books in increasing order.
You can notice that even if you take a book out and put it back in, except for that book, the rest of the books order doesn’t change.
So all we have to do is find an increasing sequence within the input that has the largest sum of weights, and subtract it from the sum of all weights(the amount of energy needed if you move all books).
code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<double,double> pdd;
//typedef complex<double> cpx;
#define fastio cin.tie(0)->sync_with_stdio(0); cout.tie(0);
#define all(x) x.begin(),x.end()
#define compress(x) x.erase(unique(all(x)),x.end())
#define ff first
#define ss second
#define INF 1e17
#define MAX 500010
#define SIZE 100010
#define MOD 1000000007
struct Segtree{
ll tree[4*100010];
Segtree(){
memset(tree,0LL,sizeof(tree));
}
void update(ll n, ll s, ll e, ll i, ll v){
if(i<s||i>e) return;
if(s==e){
tree[n] = v;
return;
}
ll m = (s+e)>>1;
update(2*n,s,m,i,v);
update(2*n+1,m+1,e,i,v);
tree[n] = max(tree[2*n],tree[2*n+1]);
}
ll query(ll n, ll s, ll e, ll l, ll r){
if(r<s||l>e) return 0;
if(l<=s&&e<=r) return tree[n];
ll m = (s+e)>>1;
return max(query(2*n,s,m,l,r),query(2*n+1,m+1,e,l,r));
}
};
Segtree seg;
ll n,w[100010],a[100010],dp[100010];
int main(){
fastio;
seg = Segtree();
cin >> n;
ll ans = 0;
for(int i=1;i<=n;i++){
cin >> w[i];
ans += 2*w[i];
}
for(int i=1;i<=n;i++){
cin >> a[i];
dp[i] = seg.query(1,1,n,1,a[i]-1) + w[a[i]];
seg.update(1,1,n,a[i],dp[i]);
}
//cout << ans << " " << seg.tree[1] << "\n";
cout << ans-2*seg.tree[1];
}