#include <iostream>
#include <vector>
#include <set>
using namespace std;
const int mx = 100'000;
using vi = vector<int>;
using pii = pair<int, int>;
struct segtree
{
vi l = vi((1<<18) + 1);
vi r = vi((1<<18) + 1);
vi mn = vi((1<<18) + 1, 0); //change to long long if error
vi lp = vi((1<<18) + 1, 0);
void build(int i, int L, int R)
{
l[i] = L;
r[i] = R;
mn[i] = lp[i] = 0;
if(l[i] == r[i])
return;
int m = (l[i] + r[i])/2;
build(2*i, l[i], m);
build(2*i+1, m+1, r[i]);
}
void add(int i, int L, int R, int V)
{
if(r[i] < L || R < l[i])
return;
// cerr << "add " << i << ' ' << l[i] << ' ' << r[i] << " : " << L << ' ' << R << ' ' << V << '\n';
if(L <= l[i] && r[i] <= R)
{
lp[i] += V;
mn[i] += V;
}
else
{
add(2*i, L, R, V);
add(2*i+1, L, R, V);
mn[i] = lp[i] + min(mn[2*i], mn[2*i+1]);
}
}
int rangemin(int i, int L, int R)
{
// cerr << "rangemin " << i << ' ' << l[i] << ' ' << r[i] << " : " << L << ' ' << R << '\n';
if(r[i] < L || R < l[i])
{
// cerr << "case 1\n";
return 1'000'000'000;
}
else if(L <= l[i] && r[i] <= R)
{
// cerr << "case 2\n";
return mn[i];
}
else
{
// cerr << "case 3\n";
return lp[i] + min(rangemin(2*i, L, R), rangemin(2*i+1, L, R));
}
}
};
int N;
segtree S;
vi X, H, V;
multiset<int> elves, children;
void output()
{
for(int i = 0; i <= N; i++)
cerr << S.rangemin(1, i, i) << ' ';
cerr << '\n';
}
void addelf(int i)
{
// cerr << "add elf " << i << '\n';
// elves.insert(i);
S.add(1, i, N, -1);
// output();
}
void removeelf(int i)
{
// cerr << "remove elf " << i << '\n';
// elves.erase(elves.find(i));
S.add(1, i, N, +1);
// output();
}
void addchild(int i)
{
// cerr << "pre : " << S.rangemin(1, 0, 0) << '\n';
// cerr << "add child " << i << '\n';
// children.insert(i);
S.add(1, i, N, +1);
// output();
// cerr << "post : " << S.rangemin(1, 0, 0) << '\n';
}
void removechild(int i)
{
// cerr << "remove child " << i << '\n';
// children.erase(children.find(i));
S.add(1, i, N, -1);
// output();
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int T;
cin >> T;
for(int t = 1; t <= T; t++)
{
cin >> N;
S.build(1, 0, N); //could bad values be accessed from previous tests? check if WA
// cerr << "pre pre : " << S.rangemin(1, 0, 0) << '\n';
// output();
X = H = V = vi(1+N);
int maxelf = 0;
for(int i = 1; i <= N; i++)
cin >> X[i];
for(int i = 1; i <= N; i++)
{
cin >> H[i];
if(H[i] == 0)
maxelf = max(maxelf, i);
}
for(int i = 1; i <= N; i++)
cin >> V[i];
vi D(1+N, -1);
int jm = 0; //J - 1
set<pii> gifts;
// cerr << "Maxelf = " << maxelf << '\n';
vi remgift(1+N, -1);
for(int i = 0; i <= N; i++)
{
// cerr << "i = " << i << '\n';
// cerr << H[i] << '\n';
if(i >= 1)
{
if(H[i] == 0) //elf
{
// newgift[i].push_back(i);
gifts.insert({V[i], i});
// cerr << "adding elf : " << i << '\n';
addelf(V[i]);
}
else //child
{
auto it = gifts.lower_bound({V[i], -1});
if(it != gifts.end())
{
remgift[i] = it->second;
gifts.erase(it);
// cerr << "removing elf : " << remgift[i] << '\n';
removeelf(V[remgift[i]]);
}
}
}
}
// for(int i = N-1; i >= 0; i--)
for(int i2 = N; i2 >= maxelf; i2--)
{
// for(int i2 = i+1; i2 <= N; i2++)
// for(int z = i2+1; z <= N; z++)
// {
if(i2 < N)
{
if(H[i2+1] == 0)
removeelf(V[i2+1]);
else if(remgift[i2+1] >= 1)
addelf(V[remgift[i2+1]]);
}
// }
for(int i = i2-1; i >= 0; i--)
{
if(H[i+1] == 0)
removeelf(V[i+1]);
else if(remgift[i+1] >= 1)
addelf(V[remgift[i+1]]);
if(H[i+1] == 0)
addelf(V[i+1]);
else
addchild(V[i+1]);
if(i2 >= maxelf)
if(S.mn[1] >= 0)
if(D[i2] == -1 || X[i2] + (X[i2] - X[i+1]) < D[i2])
D[i2] = X[i2] + (X[i2] - X[i+1]);
}
for(int u = 1; u <= i2; u++)
{
if(H[u] == 0)
{
// removeelf(V[u]);
// addelf(V[u]);
;
}
else
{
removechild(V[u]);
if(remgift[u] >= 1)
removeelf(V[remgift[u]]);
}
}
}
for(int i = 1; i <= N; i++)
cout << D[i] << ' ';
cout << '\n';
}
}
Compilation message
santa.cpp: In function 'int main()':
santa.cpp:166:7: warning: unused variable 'jm' [-Wunused-variable]
166 | int jm = 0; //J - 1
| ^~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
4448 KB |
Output is correct |
| 2 |
Correct |
10 ms |
4456 KB |
Output is correct |
| 3 |
Execution timed out |
1089 ms |
4492 KB |
Time limit exceeded |
| 4 |
Execution timed out |
1096 ms |
4496 KB |
Time limit exceeded |
| 5 |
Execution timed out |
1098 ms |
4564 KB |
Time limit exceeded |
| 6 |
Execution timed out |
1094 ms |
4692 KB |
Time limit exceeded |
| 7 |
Execution timed out |
1051 ms |
5076 KB |
Time limit exceeded |
| 8 |
Execution timed out |
1097 ms |
5460 KB |
Time limit exceeded |
| 9 |
Execution timed out |
1094 ms |
6604 KB |
Time limit exceeded |
| 10 |
Execution timed out |
1085 ms |
6644 KB |
Time limit exceeded |
