#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
using namespace std;
typedef pair<int,int> ii;
typedef long long lint;
struct node{
int s, e, m;
node *l, *r;
int val = 0; int lazy = 0;
node(int S, int E){
s = S, e = E, m = (s+e)/2;
if(s != e){
l = new node(s, m);
r = new node(m+1, e);
}
}
void apply(int L){
val += L;
lazy += L;
}
void push(){
if(s == e) return;
l->apply(lazy);
r->apply(lazy);
lazy = 0;
}
void update(int S, int E, int V){
push();
if(S == s && e == E){
apply(V);
return;
}
else if(E <= m) l->update(S,E,V);
else if(S >= m+1) r->update(S,E,V);
else{
l->update(S,m,V); r->update(m+1,E,V);
}
val = min(l->val, r->val);
}
int query(int S, int E){
push();
if(S == s && e == E) return val;
else if(E <= m) return l->query(S,E);
else if(S >= m+1) return r->query(S,E);
else{
return min(l->query(S,m), r->query(m+1,E));
}
}
} *root;
const int give = 0, take = 1;
signed main(){
freopen("i.txt","r",stdin);
ios_base::sync_with_stdio(false); cin.tie(0);
int TC; cin >> TC;
while(TC--){
int n; cin >> n;
int X[n], type[n], V[n];
int lastGive = -1;
for(int i = 0;i < n;i++) cin >> X[i];
for(int i = 0;i < n;i++) cin >> type[i];
for(int i = 0;i < n;i++) cin >> V[i];
root = new node(1, n);
for(int i = 0;i < n;i++){
if(type[i] == give) lastGive = i;
}
for(int i = 0;i <= lastGive;i++){
if(type[i] == give) root->update(V[i], n, -1);
else root->update(V[i], n, 1);
}
int ans[n]; fill(ans, ans+n, -1);
int R = lastGive+1;
multiset<int> beforeL;
for(int L = 0;L < n;L++){
while(R < n){
//cout << L << " " << R-1 << ": " << root->query(1,n) << "F\n";
if(root->query(1,n) >= 0) break;
if(type[R] == give) root->update(V[R], n, -1);
else root->update(V[R], n, 1);
R++;
}
//cout << L << " " << R-1 << "\n";
if(root->query(1,n) >= 0) ans[R-1] = L;
///do the multiset thingy
if(type[L] == give) beforeL.insert(V[L]);
else{
root->update(V[L], n, -1); ///undo previous add
auto it = beforeL.lower_bound(V[L]);
if(it == beforeL.end()) continue;
//if(L == 2) cout << *it << " " << V[L] << "\n";
root->update(*it, n, 1); ///if can find match
beforeL.erase(it);
}
}
for(int i = 0;i < n;i++){
if(i != 0) ans[i] = max(ans[i], ans[i-1]);
if(ans[i] == -1) cout << -1 << " ";
else{
cout << 2*X[i] - X[ans[i]] << " ";
}
}
cout << "\n";
}
}
Compilation message
santa.cpp: In function 'int main()':
santa.cpp:63:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen("i.txt","r",stdin);
~~~~~~~^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
11 ms |
6784 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Runtime error |
11 ms |
6784 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Runtime error |
16 ms |
6912 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Runtime error |
12 ms |
6784 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Runtime error |
12 ms |
6784 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Runtime error |
17 ms |
6784 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 7 |
Runtime error |
13 ms |
6912 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 |
Runtime error |
11 ms |
6784 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 9 |
Runtime error |
10 ms |
6784 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 10 |
Runtime error |
10 ms |
6784 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
