문제 링크 :www.acmicpc.net/problem/8217
문제 태크
PBS, Segment Tree
문제 풀이
이 문제에 사용되어질 알고리즘을 어느정도 스포를 당하고 시작했다. 하지만 내가 딱 1번밖에 짜보지 못했던 알고리즘이고, 문제가 꽤나 웰노운이라고 들어서, 풀이의 나머지 부분을 완성하려고 하였다.
pbs를 통해서 분리 횟수가 logQ이고 한 번 분리할 때마다 판별을 N개 해야하기 때문에 벌써 $O(NlgQ)$라는 시간복잡도가 형성되었다. 그래서 나의 1차 목표는 1개의 국가에 대해서 특정한 시점에 대해서 O(1) 만에 그 시점에 정해진 운석량을 모았는지 판별하는 것이다. 혹은 log의 시간복잡도에 해야할 것이다.
하지만 구간 쿼리가 주어지기 때문에 너무 Segment Tree를 쓰고 싶었고, 시간 제한을 보고 나서 로그 제곱을 유도 했다고 생각을 했다. 하지만 중요한 것은, 업데이트는 세그로 되는데, 판단이 되냐는 것이었다. 이 부분에 대해서 좀 고민을 해보다가 내가 고민할 필요하 그다지 없었다는 것을 깨달았다. 굉장히 Naive하게 나라 i에 대해서 i가 담당하는 모든 구역에 대해서 값을 모두 더하는 것으로 유성의 총 개수를 파악해도 문제가 없었다. 왜냐하면 1번의 분리 과정에서 각 구역을 1번씩만 보기 때문에 1번의 분리 과정에서 총 M번의 확인만 하는 것은 변하지 않기 때문이다.
세그를 쓰는 과정에서 구간에 값을 더하고, 한 노드의 값을 얻는 두 가지 행동을 하기를 원한다. 혹시 몰라 시간을 줄이기 위해, lazy propagation을 쓰지 않기 위해서 시작점에 업데이트, 끝 다음점에 역으로 업데이트로 구간 업데이트를 대신했고, prefix의 구간 합을 구하는 것으로 값을 얻었다. 또한 li>ri 인 경우에는 구간을 1~ri li~m으로 쪼개서 생각을 했다.
하지만, TLE가 났다. Lazy를 쓰지 않으면 충분히 빠를 것이라고 생각했는데 그러지 않았다. 내가 PBS를 별로 짜본적이 없기 때문에 내가 짠 PBS에 문제가 있는지 의심을 해봤지만, 어떻게 고쳐야 할 지 알 수가 없어서 좀 더 확실하게 시간 단축이 되는 Segment Tree -> Fenwick Tree를 수정하였다. 그리고 거의 맞을 수 있었다.
사실은 그러고도 틀렸었다. 하지만, 이 부분은 유성을 푼 사람은 다들 한 번씩 틀리는 부분이라고 생각한다. 이 문제 자체, 알고리즘에 집중을 하다보면 굉장히 기초적인 것을 잊게 된다. 코드는 최종 전 코드를 올릴려고 한다.
코드
|
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
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
|
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> pii;
#define ff first
#define ss second
#define ep emplace_back
#define eb emplace
#define pb push_back
ll arr[1010101];
ll fin[1010101];
vector<ll> v[1010101];
ll ls[1010101];
ll le[1010101];
ll ans[1010101];
ll vis[1010101];
struct poi{
ll lu,ru,au;
};
poi qwer[1010101];
void pre(ll s,ll e){
if(e<=s) return;
ll mid=(s+e)/2;
ls[mid]=s;
le[mid]=e;
pre(mid+1,e);
pre(s,mid);
}
vector<ll> q1[1010101];
vector<ll> vn[101];
ll nn=2222222;
ll tree[4040404];
void upt(ll idx, ll val){
while(idx<=nn){
tree[idx]+=val;
idx+=idx&-idx;
}
}
ll sum(ll x){
ll val=tree[x];
while(x-=x&-x) val+=tree[x];
return val;
}
ll sol(ll l, ll r){
return sum(r)-sum(l-1);
}
int main(){
ll i,j,k,l,m,n;
scanf("%lld %lld",&n,&m);
for(i=1;i<=m;i++){
scanf("%lld",&k);
v[k].pb(i);
}
for(i=1;i<=n;i++)
scanf("%lld",&fin[i]);
ll q;
scanf("%lld",&q);
for(i=1;i<=q;i++)
scanf("%lld %lld %lld",&qwer[i].lu,&qwer[i].ru,&qwer[i].au);
pre(1,q+1);
for(i=1;i<=n;i++)
q1[q/2+1].pb(i);
ll t;
vn[1].pb(q/2+1);
for(t=1;t<=22;t++){
//printf("%lld\n",t);
sort(vn[t].begin(), vn[t].end());
vn[t].erase(unique(vn[t].begin(), vn[t].end()),vn[t].end());
//printf("%lld\n",t);
ll fl=1;
for(auto k:vn[t]){
if(q1[k].size()==0||le[k]==0||vis[k]) continue;
// printf("%lld %lld\n",t,k);
vis[k]=1;
while(fl<=k){
ll lu=qwer[fl].lu;
ll ru=qwer[fl].ru;
ll au=qwer[fl].au;
if(qwer[fl].lu<=qwer[fl].ru){
upt(lu,au);
upt(ru+1,-au);
}
else{
upt(lu,au);
upt(ru+1,-au);
upt(1,au);
}
fl++;
}
// for(ll p=1;p<=9;p++)
// printf("%lld ",tree[p]);
// printf("\n");
for(auto a:q1[k]){
ll val=0;
for(auto b:v[a]){
val+=sum(b);
// printf("%lld %lld %lld\n",a,b,val);
}
// printf("aval %lld %lld\n",a,val);
if(val>=fin[a]){
if(k<=ls[k]) ans[a]=k;
else q1[(ls[k]+k)/2].pb(a);
}
else{
if(k+1>=le[k]) ans[a]=k+1;
else q1[(le[k]+k+1)/2].pb(a);
}
}
vn[t+1].pb((ls[k]+k)/2);
vn[t+1].pb((le[k]+k+1)/2);
}
for(ll p=1;p<=2323232;p++)
tree[p]=0;
}
/*for(i=1;i<=q+1;i++){
for(auto k:q1[i]) ans[k]=i;
}
*/
for(i=1;i<=n;i++){
if(ans[i]<=q) printf("%lld\n",ans[i]);
else printf("NIE\n");
}
}
|
'코딩 > 백준 문제 풀이' 카테고리의 다른 글
| BOJ 14898 - 서로 다른 수와 쿼리 2 (2) | 2020.11.19 |
|---|---|
| BOJ 10806 - 공중도시 (0) | 2020.11.09 |
| IOI 2020 day2 - stations (0) | 2020.10.17 |
| IOI 2020 day1 - Carnival Tickets (0) | 2020.10.11 |
| IOI 2020 day1 - Connecting Supertrees (0) | 2020.10.07 |