I need other topics to write about
Driving Exam
Polish Olympiad in Informatics(POI) 2006/2007 Stage 3 #4
In this problem you are given some vertical roads that point upward, and horizontal roads of length 1 that point right or left. When all roads are one way, you will be able to reach all vertical roads by starting at the bottom of some roads, while not on others. Lets call these(the roads that lead to all other roads) Super Roads. The goal of this problem is to find the maximum number of new Super Roads you can make by adding $K$ horizontal rows.
To begin, we can figure out that any vertical road between two Super Roads are also Super Roads. This isn’t too hard to prove. This fact allows a two-pointer approach to solve the problem. We can use two pointers to keep track of two roads we will make into Super Roads, and if it takes less than or equal to $K$ roads to make it like that, we can update our answer.
For two roads into Super Roads, you must be able to reach the far right from the left road, and the far left from the right road. Since all vertical roads point up, there has to be a sequence of horizontal roads where the location of the roads keep increasing. Therefore, by keeping track of the longest increasing subsequence of the roads, we can easily find the number of roads needed to make a road reach the far left or far right.
Now we can find the maximum numbers of Super Roads when $K$ roads are added, using the two-pointer method above, since we know how many roads are necessary to add using the LIS stuff. So we find the number for $K$ roads added, and subtract the number for no roads added, and we get our answer.
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
struct Segtree{
ll tree[4*100010];
void init(){
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,m,p,k;
vector<pll> v[2];
ll l[100010],r[100010],dp1[100010],dp2[100010];
ll solve(ll x){
ll ans = 0, rp = 0;
for(int i=n-1;i>=0;i--){
while(rp<n-1&&l[i]+r[rp+1]<=x) rp++;
if(l[i]+r[rp]<=x) ans = max(ans,rp+1-(n-i-1));
}
return ans;
}
int main(){
fastio;
cin >> n >> m >> p >> k;
for(int i=0;i<p;i++){
ll x,y,z; cin >> x >> y >> z;
if(z) v[1].push_back({m-y,x});
else v[0].push_back({m-y,n-x});
}
sort(all(v[1])); sort(all(v[0]));
for(int i=0;i<100010;i++){
l[i] = 1e9+1LL;
r[i] = 1e9+1LL;
}
l[0] = 0;
r[0] = 0;
seg.init();
for(int i=0;i<(ll)v[0].size();i++){
dp1[i] = seg.query(1,1,n,1,v[0][i].ss-1) + 1;
seg.update(1,1,n,v[0][i].ss,dp1[i]);
l[v[0][i].ss] = min(l[v[0][i].ss],v[0][i].ss - dp1[i]);
}
seg.init();
for(int i=0;i<(ll)v[1].size();i++){
dp2[i] = seg.query(1,1,n,1,v[1][i].ss-1) + 1;
seg.update(1,1,n,v[1][i].ss,dp2[i]);
r[v[1][i].ss] = min(r[v[1][i].ss],v[1][i].ss - dp2[i]);
}
for(int i=1;i<n;i++){
l[i] = min(l[i],l[i-1]+1);
r[i] = min(r[i],r[i-1]+1);
}
//cout << solve(0) << "\n";
cout << solve(k)-solve(0);
}
루트 노드가 많은 트리일수록 좋은 트리이다
Baekjoon Online Judge(BOJ) #24272
In this problem, you are given a tree-shaped graph where the edges can be one directional, or bidirectional. We define a node a root if it is possible to reach all other nodes from that node. Then, you are given a number of queries where you change the type of edge(where it points, or whether it is directional). For each query, you have to print out the number of root nodes in the modified tree. Each query is accumulated.
For a directed edge, a root node can only exist on one side of the edge. If we do a DFS traversal on the tree, each node has an in order and an out order. You can notice that by changing an edge, the group of nodes that change, from can be a root to not or visa versa, can be represented as an interval of those in orders and out orders.
For an edge $u \rightarrow v$, if $u$ is the parent of $v$, the interval of nodes that cannot be a root node can be represented as $[in_v, out_v]$. If $u$ is a child of $v$, the interval of nodes that cannot be a root node can be represented as $[1,in[u]-1] \cup [e[u]+1,N]$.
There for we can use a segment tree, add 1 to all nodes that no longer can be roots, and subtract 1 if an edge allows them to be a root node. Then we can count the number of 0’s to find the answer.
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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#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], len[4*100010];
Segtree(){
memset(tree,0LL,sizeof(tree));
memset(len,0LL,sizeof(len));
}
void update(ll n, ll s, ll e, ll l, ll r, ll v){
if(r<s||l>e) return;
if(l<=s&&e<=r){
tree[n] += v;
}
else{
ll m = (s+e)>>1;
update(2*n,s,m,l,r,v);
update(2*n+1,m+1,e,l,r,v);
}
if(tree[n]>0) len[n] = e-s+1;
else if(s==e) len[n] = 0;
else len[n] = len[2*n]+len[2*n+1];
}
ll query(){
return len[1];
}
};
ll n,q,c;
ll s[100010],e[100010],par[100010];
vector<ll> g[100010];
map<pll,string> mp;
Segtree seg = Segtree();
void dfs(ll x, ll p=0){
par[x] = p;
s[x] = ++c;
for(auto i:g[x]){
if(!s[i]) dfs(i,x);
}
e[x] = c;
}
void change(ll u, ll v, ll x){
if(u==par[v]){
seg.update(1,1,n,s[v],e[v],x);
}
else{
seg.update(1,1,n,1,s[u]-1,x);
seg.update(1,1,n,e[u]+1,e[1],x);
}
}
int main(){
fastio;
cin >> n;
vector<pll> tmp;
for(int i=1;i<n;i++){
ll x,y;
string s;
cin >> x >> s >> y;
g[x].push_back(y);
g[y].push_back(x);
if(s=="->"){
mp[{x,y}] = "->";
mp[{y,x}] = "<-";
tmp.push_back({x,y});
}
else if(s=="<-"){
mp[{y,x}] = "->";
mp[{x,y}] = "<-";
tmp.push_back({y,x});
}
else{
mp[{x,y}] = mp[{y,x}] = "--";
}
}
dfs(1);
for(auto i:tmp){
ll u = i.ff, v = i.ss;
change(u,v,1);
}
cin >> q;
while(q--){
ll u,v;
string s;
cin >> u >> s >> v;
string bs = mp[{u,v}];
if(bs=="->"){
change(u,v,-1);
}
else if(bs=="<-"){
change(v,u,-1);
}
if(s=="->"){
mp[{u,v}] = "->";
mp[{v,u}] = "<-";
change(u,v,1);
}
else if(s=="<-"){
mp[{u,v}] = "<-";
mp[{v,u}] = "->";
change(v,u,1);
}
else{
mp[{u,v}] = mp[{v,u}] = "--";
}
cout << n-seg.query() << "\n";
}
}
JOI 国のお祭り事情 (Festivals in JOI Kingdom)
Japanese Olympiad in Informatics(JOI) 2012 #5
In this problem you are given a weighted graph. Some nodes in the graph have festivals going on. In each query, you are given a start node and an end node, and must output the farthest minimum distance on a route from the start node to the end node.
This problem is obviously a binary search problem. But since we have to do it many times, we can use a parallel binary search approach to solve this problem.
We can use Dijkstra’s algorithm to find the minimum distance from each node to a festival. Then we can use PBS to find the answer to all queries, using union-find to merge cities we can move to.
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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#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 DSU{
ll par[100010], vis[100010];
void init(){
for(int i=0;i<100010;i++){
par[i] = i;
vis[i] = 0;
}
}
ll find(ll x){
if(x==par[x]) return x;
return par[x] = find(par[x]);
}
ll onion(ll a, ll b){
a = find(a); b = find(b);
if(vis[a]+vis[b]!=2) return 0;
if(a==b) return 0;
par[a] = b;
return 1;
}
};
pll qry[100010];
ll l[100010],r[100010],ans[100010],dist[100010];
DSU dsu;
vector<pll> g[100010];
vector<ll> pbs[100010],nd[100010];
priority_queue<pll> pq;
void dijkstra(){
while(!pq.empty()){
ll cur = pq.top().ss, w = -pq.top().ff;
pq.pop();
if(dist[cur]<w) continue;
for(auto i:g[cur]){
if(dist[i.ff]>w+i.ss){
dist[i.ff] = w+i.ss;
pq.push({-dist[i.ff],i.ff});
}
}
}
}
int main(){
fastio;
ll n,m,k,q; cin >> n >> m >> k >> q;
for(int i=0;i<m;i++){
ll x,y,z; cin >> x >> y >> z;
g[x].push_back({y,z});
g[y].push_back({x,z});
}
for(int i=1;i<=n;i++){
dist[i] = 1e15+1LL;
}
for(int i=1;i<=k;i++){
ll x; cin >> x;
dist[x] = 0;
pq.push({0,x});
}
dijkstra();
vector<ll> tmp; tmp.push_back(-1);
for(int i=1;i<=n;i++){
//cout << i << " " << dist[i] << "\n";
tmp.push_back(dist[i]);
}
sort(all(tmp));
compress(tmp);
ll sz = tmp.size();
for(int i=1;i<=n;i++){
ll idx = lower_bound(all(tmp),dist[i]) - tmp.begin();
nd[idx].push_back(i);
}
for(int i=1;i<=q;i++){
cin >> qry[i].ff >> qry[i].ss;
l[i] = 0; r[i] = sz;
ll m = (l[i]+r[i])/2;
pbs[m].push_back(i);
}
for(int t=1;t<=20;t++){
dsu.init();
for(int i=sz-1;i>=1;i--){
for(auto j:nd[i]){
dsu.vis[j] = 1;
for(auto k:g[j]){
dsu.onion(j,k.ff);
}
}
for(auto j:pbs[i]){
if(dsu.find(qry[j].ff)==dsu.find(qry[j].ss)){
ans[j] = max(ans[j],(ll)i);
l[j] = i+1;
}
else r[j] = i-1;
}
pbs[i].clear();
}
for(int i=1;i<=q;i++){
if(l[i]<=r[i]){
pbs[(l[i]+r[i])/2].push_back(i);
}
}
}
for(int i=1;i<=q;i++){
cout << max(tmp[ans[i]],0LL) << "\n";
}
}
Conspiracy
Polish Olympiad in Informatics(POI) 2011/2012 Stage 1 #1
In this problem you are given a graph, and must find the number of ways to partition the nodes into two groups so that in one group, all nodes are connected to each other(a clique), and in another, all nodes are not connected to one another(an independent set).
Lets call the degree of a node $v$ as $deg_v$. For $N$ nodes in order, lets say the first $k$ nodes are in the independent set, and the rest are in the clique. Here, we can figure out two things:
- $deg_u \leq deg_v \quad (1 \leq u \leq k, \space k+1 \leq v \leq N)$
- $\sum_{v = k+1}^N deg_v = \sum_{u = 1}^k deg_u + (N-k)(N-k-1)$
Therefore we can order the vertices in order of increasing degree, then loop through the nodes, dividing the ones prior into the independent set, and the other ones into the clique. For nodes with the same degree, we have to select some, making the need for combination. I used a $N^2$ table, but because the memory limit is a bit tight, I used the integer type for all variables instead of long long, which I normally use.
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
#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
int n,deg[5010],lo[5010],hi[5010];
int dp[5010][5010];
ll c(ll n, ll r){
if(n==r||r==0) return 1;
int &ret = dp[n][r];
if(ret) return ret;
return ret = c(n-1,r)+c(n-1,r-1);
}
int main(){
fastio;
cin >> n;
ll sum = 0;
for(int i=1;i<=n;i++){
ll x; cin >> x;
deg[i] = x;
sum += x;
for(int j=0;j<x;j++){
ll y; cin >> y;
}
}
sort(deg+1,deg+1+n);
for(int i=0;i<5010;i++){
lo[i] = 1e9;
}
for(int i=1;i<=n;i++){
lo[deg[i]] = min(lo[deg[i]],i);
hi[deg[i]] = max(hi[deg[i]],i);
}
ll l = 0, r = sum, ans = 0;
for(int i=1;i<n;i++){
l += deg[i];
r -= deg[i];
if(r==l+(n-i)*(n-i-1)){
ll tot = hi[deg[i]] - lo[deg[i]] + 1;
ll cur = i - lo[deg[i]] + 1;
ans += c(tot,cur);
}
}
cout << ans;
}
Commemorative Race
Mid-Central Regional Programming Contest 2019 #B
In this problem, your given a DAG, and you have to find the shortest path you can earn by cutting an edge and rerouting a path with the longest edge right before the edge that has been cut. The problem is a little complicated.
By doing a DFS traversal, we can recursively find the longest path starting from a node, as well as the second longest path that uses an edge other than the one used by the longest path.
Then we can start a second traversal, this time finding the longest path when the edge is cut. We must check how many ways the node of the cut edge can reach, because if can be reached in more than one way, cutting the current edge will be useless. After cutting it, the longest path available will be the second longest path we found earlier.
Also to make life easier, it is possible to create a new node and connect it to all other nodes. This way we don’t have to worry about running the traversal multiple times.
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
ll n,m,d[100010],d2[100010],vis[100010],cnt[100010],ans[100010];
vector<ll> g[100010];
void dfs(ll x){
vis[x] = 1;
for(auto i:g[x]){
if(!vis[i]) dfs(i);
ll nd = d[i]+1;
if(nd>d[x]){
d2[x] = d[x];
d[x] = nd;
}
else d2[x] = max(d2[x],nd);
}
}
void dfs2(ll x, ll dep){
vis[x] = 1;
for(auto i:g[x]){
if(d[x]==d[i]+1){
if(!vis[i]) dfs2(i,dep+1);
cnt[dep]++;
ans[dep] = dep+d2[x];
}
}
}
int main(){
fastio;
cin >> n >> m;
for(int i=0;i<m;i++){
ll x,y; cin >> x >> y;
g[x].push_back(y);
}
for(int i=1;i<=n;i++){
g[0].push_back(i);
}
dfs(0);
memset(vis,0,sizeof(vis));
dfs2(0,0);
ll an = d[0];
//cout << an-1 << "\n";
for(int i=1;i<=n;i++){
if(cnt[i]==1) an = min(an,ans[i]);
}
cout << an-1;
}
별이 빛나는 밤에
Baekjoon Online Judge(BOJ) #18252
In this problem you are given rails parallel to the x axis, and the location of two stars(the top star and the bottom star). There is one star per rail, and the problem is to find the smallest possible area of the largest triangle you can earn by connecting three stars. Each star can move on the rails.
Obviously, the most ideal placement of stars would be to place them on the line connecting the top and bottom stars(if possible), or placing the star as near to the line as possible. The rigorous proof of this is written in this paper.
Now we now the placement of stars, we just have to find the largest triangle. Since the vertices of the largest triangle will be on the convex hull, we can first compute that. Then we can try every possible line for one edge of the triangle, while using a two-pointer approach to keep track of the third vertex. This way we can solve this problem in $O(N^2)$.
On a side note this problem can be solved in $O(NlogN)$ and also $O(N)$. I’ll list some papers below. I might read them. Or not.
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
#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{
double x, y;
bool operator < (const P &p) const {
if(x!=p.x) return x<p.x;
return y<p.y;
}
};
double ccw(P a, P b, P c){
return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
double area(P a, P b, P c){
return abs(ccw(a,b,c));
}
vector<P> convexhull(vector<P> &p){
ll n = p.size(), k = 0;
if(n<3) return p;
if(n==3){
if(ccw(p[0],p[1],p[2])<0) reverse(all(p));
return p;
}
vector<P> h(2*n);
sort(all(p));
for(int i=0;i<n;i++){
while(k>=2&&ccw(h[k-2],h[k-1],p[i])<=0) k--;
h[k++] = p[i];
}
for(int i=n-1,t=k+1;i>0;i--){
while(k>=t&&ccw(h[k-2],h[k-1],p[i-1])<=0) k--;
h[k++] = p[i-1];
}
h.resize(k-1);
return h;
}
ll n, x1, yy, x2, y2;
vector<P> inp;
int main(){
fastio;
cin >> n;
cin >> x1 >> yy >> x2 >> y2;
inp.push_back({1.0*x1,1.0*yy});
inp.push_back({1.0*x2,1.0*y2});
for(int i=0;i<n;i++){
ll y,s,e; cin >> y >> s >> e;
double sl = 1.0*(yy-y2)/(x1-x2);
double x = 1.0*(y+sl*x1-yy)/sl;
if(s<=x&&x<=e) continue;
else if(s>x) inp.push_back({1.0*s,1.0*y});
else if(e<x) inp.push_back({1.0*e,1.0*y});
}
vector<P> ch = convexhull(inp);
ll sz = ch.size();
double ans = 0;
for(int i=0;i<sz;i++){
ll p = i+1;
for(int j=i+2;j<sz;j++){
while((p+1)%sz!=j&&area(ch[i],ch[j],ch[p])<=area(ch[i],ch[j],ch[p+1]))
p = (p+1)%sz;
double cur = area(ch[i],ch[j],ch[p]);
//cout << cur << "\n";
ans = max(ans,cur);
}
}
cout.precision(10);
cout << fixed << ans/2;
}
Cloakroom
Polish Olympiad in Informatics 2011/2012 Stage 2 #3
In this problem you are given $N$ items with their value, the time their put into the room, and the time their taken from the room. Then you are given $P$ plans consisting of an integer $k$, the start time, and the duration of the plan. The problem is to find, for all plans, whether it is possible to gather items so that the sum of the values is exactly $k$, and all items stay present during the plan.
First thing that comes to mind is the knapsack problem. Since $k \leq 100,000$, we can maintain an array that checks whether it is possible to make some certain amount. The problem is that not all items can be taken at once, and we can’t update the array a million times.
Actually, since $P \leq 1,000,000$, it is quite hard to do anything for every plan. But $N \leq 1,000$, so maybe we can do something for every item.
First lets sort the plans and items based on their starting time, because that just makes life easier. Then, for an item, any plan that has a start time before the start time of the item cannot take the item and every item that comes after it(because everything is sorted in increasing start time). Sadly, the same can’t be done for end times.
Lets define an array $dp$. Initially we only checked whether it is possible to make a certain amount. Instead, lets make it so that $dp_k$ is the latest time possible to make $k$. Then $dp_i = max(dp_i, min(dp_{i-k},e))$ for every $k \leq i \leq 100,000$, when $e$ is the ending time of the item. Then we can know if a plan is possible by checking if $dp_k > e$, this time $e$ being the ending time of the plan.
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
#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 Item{
ll s, e, c;
bool operator < (const Item &i) const {
return s<i.s;
}
};
struct Plan{
ll s, e, k, i;
bool operator < (const Plan &p) const {
return s<p.s;
}
};
ll n,q,dp[100010],ans[1000010];
Item a[1010];
Plan p[1000010];
int main(){
fastio;
cin >> n;
for(int i=1;i<=n;i++){
ll x,y,z; cin >> x >> y >> z;
a[i] = {y,z,x};
}
cin >> q;
for(int i=1;i<=q;i++){
ll x,y,z; cin >> x >> y >> z;
p[i] = {x,x+z,y,i};
}
sort(a+1,a+1+n);
sort(p+1,p+1+q);
ll cur = 1;
for(int i=1;i<100010;i++){
dp[i] = -(ll)1e15;
}
dp[0] = (ll)1e15;
for(int i=1;i<=n;i++){
while(cur<=q&&p[cur].s<a[i].s){
if(dp[p[cur].k]>p[cur].e) ans[p[cur].i] = 1;
cur++;
}
for(int j=100000;j>=a[i].c;j--){
dp[j] = max(dp[j],min(dp[j-a[i].c],a[i].e));
}
}
while(cur<=q){
if(dp[p[cur].k]>p[cur].e) ans[p[cur].i] = 1;
cur++;
}
for(int i=1;i<=q;i++){
if(ans[i]) cout << "TAK\n";
else cout << "NIE\n";
}
}
히스토그램에서 가장 큰 직사각형과 쿼리
Baekjoon Online Judge(BOJ) #16977
In this problem, you are given a histogram and some queries. For each query, you have to find the height of the largest rectangle with a width of $w$ you can make using only the rectangles in range $[l, r]$ in the histogram.
Since the width is already chosen, the problem can be changed into finding the largest height a rectangle can have within the range, which is what we wanted to find anyway. When there is only a single query, this problem can be solved using binary search. We can use a segment tree where indices with a rectangle height of larger than some threshold(in the histogram) has a value of 1, and others have some small value. Then we can find the largest subset sum in the array using the segment tree.
But there are multiple queries. Still we just have to do the whole thing, just using PBS.
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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#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 Node{
ll lmax, rmax;
ll tmax, sum;
};
struct Segtree{
Node tree[4*100010];
Node null = {-(ll)1e11,-(ll)1e11,-(ll)1e11,-(ll)1e11};
Segtree(){
for(int i=0;i<4*100010;i++){
tree[i] = null;
}
}
Node merge(const Node &a, const Node &b){
Node ret = null;
ret.lmax = max(a.lmax, a.sum + b.lmax);
ret.rmax = max(a.rmax + b.sum, b.rmax);
ret.sum = a.sum + b.sum;
ret.tmax = max({ret.lmax, ret.rmax, a.rmax + b.lmax, a.tmax, b.tmax});
return ret;
}
void update(ll n, ll s, ll e, ll i, ll v){
if(i<s||i>e) return;
if(s==e){
tree[n] = {1,1,1,1};
return;
}
ll m = (s+e)>>1;
update(2*n,s,m,i,v);
update(2*n+1,m+1,e,i,v);
tree[n] = merge(tree[2*n],tree[2*n+1]);
}
Node query(ll n, ll s, ll e, ll l, ll r){
if(r<s||l>e) return null;
if(l<=s&&e<=r) return tree[n];
ll m = (s+e)>>1;
return merge(query(2*n,s,m,l,r),query(2*n+1,m+1,e,l,r));
}
};
struct Q{
ll l,r,w;
};
Q qry[100010];
ll n,q,a[100010],ca[100010];
ll l[100010],r[100010],ans[100010];
vector<ll> ht,g[100010],nh[100010];
int main(){
fastio;
cin >> n;
for(int i=1;i<=n;i++){
cin >> a[i];
ht.push_back(a[i]);
}
sort(all(ht)); compress(ht);
ll sz = ht.size();
for(int i=1;i<=n;i++){
ca[i] = lower_bound(all(ht),a[i])-ht.begin()+1;
nh[ca[i]].push_back(i);
}
cin >> q;
for(int i=1;i<=q;i++){
ll l,r,w; cin >> l >> r >> w;
qry[i] = {l,r,w};
}
for(int i=1;i<=q;i++){
l[i] = 1;
r[i] = sz;
}
for(;;){
Segtree seg = Segtree();
for(int i=0;i<100010;i++){
g[i].clear();
}
ll f = 0;
for(int i=1;i<=q;i++){
if(l[i]<=r[i]){
f = 1;
g[(l[i]+r[i])/2].push_back(i);
}
}
if(!f) break;
for(int i=sz;i>=1;i--){
for(auto j:nh[i]){
seg.update(1,1,n,j,1);
}
for(auto j:g[i]){
ll le = qry[j].l, ri = qry[j].r, w = qry[j].w;
ll k = max(0LL,seg.query(1,1,n,le,ri).tmax);
if(k>=w){
l[j] = i+1;
ans[j] = ht[i-1];
}
else{
r[j] = i-1;
}
}
}
}
for(int i=1;i<=q;i++){
cout << ans[i] << "\n";
}
}
Strah
Croatian Open Competition in Informatics 2018/2019 Contest 1 #4
In this problem your given a grid consisting of dots(.) and hashtags(#). Every dot is assigned a value, meaning the number of rectangles that consist of only dots(lets call these good rectangles) that contains the current dot.
Instead of calculating the number of good rectangles containing each dot, we could instead calculate the sum of the areas of all good rectangles. It could be easily seen that the two are the same. For each point, were going to calculate the sum of areas of good rectangles who’s lower right corner is the current dot.
Lets use a stack. Were going to put indices into the stack so that the height of each index create a non-decreasing sequence. Here, a height of an index the number of consecutive dots above the current index, before there is #. The height can be found using a simple prefix sum array. To keep the stack non-decreasing, every time one with a smaller height than the top of the stack comes in, we can keep popping it until the top is not taller.
Lets call $dp_{i,j}$ the sum of the areas where the lower right corner is $(i,j)$. Lets say the width from the current index to the top of the index is $w$ and the current height is $h$, the index of top of the stack $k$. Every rectangle that was in $dp_{i,k}$ now has an additional length $w$ added to it. How much exactly? If we call the widths of dots starting from the bottom $w_1, w_2, w_3, \cdots$, the amount added would be $w(w_1 + 2w_2 + 3w_3 + \cdots)$. Therefore it would be a good idea to keep track of $w_1 + 2w_2 + 3w_3 + \cdots$ for every $(i,j)$ as well.
When a rectangle is added, all of the widths($w_1, w_2, w_3, \cdots$) increase by 1. There for the difference is $1 + 2 + 3 + \cdots + h = \frac{h(h+1)}{2}$. So we add that much. Other than that, there is the $w \times h$ rectangle that is not contained in $dp_{i,k}$. The sum of areas in a rectangle $n \times m$ can be found with the following:
\[\sum_{i=1}^{n} \sum_{j=1}^{m}ij = \frac{i(i+1)j(j+1)}{4}\]And by adding that we can maintain the $dp$ array, and adding all the values in the array gives us our answer.
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,m,h[2010],dp[2010][2010],cnt[2010][2010];
char a[2010][2010];
int main(){
fastio;
cin >> n >> m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin >> a[i][j];
}
}
ll ans = 0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(a[i][j]=='#') h[j] = 0;
else h[j] = h[j]+1;
}
stack<ll> st;
st.push(0);
for(int j=1;j<=m+1;j++){
ll prv = 1;
while(!st.empty()&&h[st.top()]>h[j]){
st.pop();
ll w = j - st.top() - 1;
prv = w+1;
}
dp[i][j] = dp[i][st.top()]+cnt[i][st.top()]*prv+prv*(prv+1)*h[j]*(h[j]+1)/4;
cnt[i][j] = cnt[i][st.top()]+h[j]*(h[j]+1)/2*prv;
st.push(j);
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
ans += dp[i][j];
}
}
cout << ans;
}
wow I wrote a lot