/**
* user: tinca-6db
* fname: Matei
* lname: Tinca
* task: santa
* score: 100.0
* date: 2019-10-11 10:35:45.784954
*/
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 100000;
const int INF = 1000000000;
int aint[1+4*(MAX_N+1)], lazy[1+4*(MAX_N+1)];
void pushlazy(int l, int r, int nod) {
aint[nod] += lazy[nod];
if(l < r) {
lazy[2 * nod] += lazy[nod];
lazy[2 * nod + 1] += lazy[nod];
}
lazy[nod] = 0;
}
void update(int i, int j, int val, int l = 0, int r = MAX_N, int nod = 1) {
pushlazy(l, r, nod);
if(j < l || r < i || j < i) return;
if(i <= l && r <= j) {
lazy[nod] += val;
pushlazy(l, r, nod);
} else {
int mid = (l + r) / 2;
update(i, j, val, l, mid, 2 * nod);
update(i, j, val, mid + 1, r, 2 * nod + 1);
aint[nod] = min(aint[2 * nod], aint[2 * nod + 1]);
}
}
int query(int i, int j, int l = 0, int r = MAX_N, int nod = 1) {
pushlazy(l, r, nod);
if(r < i || j < l || j < i) return INF;
if(i <= l && r <= j)
return aint[nod];
else {
int mid = (l + r) / 2;
return min(query(i, j, l, mid, 2 * nod),
query(i, j, mid + 1, r, 2 * nod + 1));
}
}
void initaint(int nod = 1, int l = 0, int r = MAX_N) {
aint[nod] = lazy[nod] = 0;
if(l < r) {
int mid = (l + r) / 2;
initaint(2 * nod, l, mid);
initaint(2 * nod + 1, mid + 1, r);
}
}
int x[1+MAX_N], h[1+MAX_N], v[1+MAX_N];
void debugAint(int N) {
printf("Aint: ");
for(int i = 0; i <= N; ++i)
printf("%d ", query(i, i));
printf("\n");
}
void solvetest() {
int N, lastElf = 0;
initaint();
scanf("%d", &N);
for(int i = 1; i <= N; ++i)
scanf("%d", &x[i]);
for(int i = 1; i <= N; ++i) {
scanf("%d", &h[i]);
if(h[i] == 0)
lastElf = i;
}
for(int i = 1; i <= N; ++i)
scanf("%d", &v[i]);
if(lastElf == 0) {
for(int i = 1; i <= N; ++i)
printf("%d ", x[i]);
printf("\n");
return;
}
int t = 0;
while(t <= N && (t < lastElf || query(0, MAX_N) < 0)) {
if(t > 0)
printf("-1 ");
++t;
if(h[t] == 0)
update(v[t], MAX_N, -1);
else
update(v[t], MAX_N, 1);
}
initaint();
for(int i = 1; i <= t; ++i) {
if(h[i] == 0)
update(v[i], MAX_N, -1);
else
update(v[i], MAX_N, 1);
}
// de la t este posibil sa faci alea alea
int left = 0; // prima locatie la care NU MA MAI INTORC
set<pair<int, int> > gifts;
for(int i = t; i <= N; ++i) {
// muta pointer
bool ok;
do {
ok = false;
if(left + 1 < i) {
if(h[left + 1] == 1) { // copil
update(v[left + 1], MAX_N, - 1);
set<pair<int, int> >::iterator it = gifts.lower_bound({v[left + 1], -1});
if(it != gifts.end()) { // ii dam copilului pe care tocmai l-am scos un cadou cat mai prost
update(it->first, MAX_N, 1);
/*if(query(0, MAX_N) >= 0) {
gifts.erase(it);
++left;
} else {
update(v[left + 1], MAX_N, 1);
update(it->first, MAX_N, -1);
}*/
}
if(query(0, MAX_N) >= 0) {
if(it != gifts.end())
gifts.erase(it);
++left;
ok = true;
} else {
update(v[left + 1], MAX_N, 1);
if(it != gifts.end())
update(it->first, MAX_N, -1);
}
} else {
gifts.insert({v[left + 1], left + 1});
++left;
ok = true;
}
}
} while(ok);
if(i + 1 <= N)
update(v[i + 1], MAX_N, 1);
printf("%d ", 2 * x[i] - x[left + 1]);
}
printf("\n");
}
int main() {
int T;
scanf("%d", &T);
while(T--)
solvetest();
return 0;
}
Compilation message
santa.cpp: In function 'void solvetest()':
santa.cpp:77:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &N);
~~~~~^~~~~~~~~~
santa.cpp:79:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &x[i]);
~~~~~^~~~~~~~~~~~~
santa.cpp:81:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &h[i]);
~~~~~^~~~~~~~~~~~~
santa.cpp:86:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &v[i]);
~~~~~^~~~~~~~~~~~~
santa.cpp: In function 'int main()':
santa.cpp:165:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &T);
~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
2432 KB |
Output is correct |
| 2 |
Correct |
16 ms |
2432 KB |
Output is correct |
| 3 |
Correct |
30 ms |
2560 KB |
Output is correct |
| 4 |
Correct |
52 ms |
2936 KB |
Output is correct |
| 5 |
Correct |
95 ms |
3576 KB |
Output is correct |
| 6 |
Correct |
141 ms |
4216 KB |
Output is correct |
| 7 |
Correct |
237 ms |
6008 KB |
Output is correct |
| 8 |
Correct |
366 ms |
7928 KB |
Output is correct |
| 9 |
Correct |
442 ms |
10104 KB |
Output is correct |
| 10 |
Correct |
647 ms |
12920 KB |
Output is correct |
