| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 79601 |
2018-10-15T05:26:54 Z |
triplem5ds |
Meteors (POI11_met) |
C++14 |
|
6000 ms |
66560 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 3e5+5;
int lo[N], hi[N];
int n, m, k;
int a[N]; ///Meteor States
int cap[N]; ///Cap for each meteor
int l[N], r[N], add[N];
int val[N];
/*
If i parallel binary search how should i handle
the L[i], R[i] updates with segment tree
*/
vector<int> corrsponds[N];
int ans[N];
vector<int> qu[N];
ll laz[N<<2];
void push(int node, int s, int e){
if(s != e){
laz[node<<1] += laz[node];
laz[node<<1|1] += laz[node];
laz[node] = 0;
}
}
void upd(int node, int s, int e, int l, int r, int v){
push(node,s,e);
if(r < s || e < l || l > r)
return;
if(l <= s && e <= r){
laz[node] += v;
push(node,s,e);
return;
}
int md = (s + e) >> 1;
upd(node<<1,s,md,l,r,v);
upd(node<<1|1,md+1,e,l,r,v);
}
ll qry(int node, int s, int e, int idx){
push(node,s,e);
if(s==e){
return laz[node];
}
int md = (s+e) >> 1;
if(idx <= md)
return qry(node<<1,s,md,idx);
else
return qry(node<<1|1,md+1,e,idx);
}
int main(){
#ifdef ONLINE_JUDGE
ios_base::sync_with_stdio(0);
cin.tie(0);
#endif // ONLINE_JUDGE
memset(ans,-1,sizeof ans);
scanf("%d%d", &n, &m);
for(int i = 0; i < m; i++){
scanf("%d", a + i); --a[i];
corrsponds[a[i]].push_back(i);
}
for(int i = 0; i < n; i++)
scanf("%d", cap + i);
scanf("%d", &k);
for(int i = 0; i < k; i++)
scanf("%lld%lld%lld", l + i, r + i, add + i), --l[i], --r[i];
for(int i = 0; i < n; i++){
hi[i] = k;
qu[(lo[i]+hi[i]) >> 1].push_back(i);
}
for(int i = 0; i < 20; i++){
// cerr << "Search : " << i << '\n';
for(int j = 0; j < k; j++){
if(l[j] <= r[j])
upd(1,0,m-1,l[j],r[j],add[j]);
else
upd(1,0,m-1,l[j],m-1,add[j]),
upd(1,0,m-1,0,r[j],add[j]);
for(auto v : qu[j]){
ll sum = 0;
for(auto x : corrsponds[v]){
sum += qry(1,0,m-1,x);
}
// cout << "Median : " << j << " Index : " << v << " Sum : " << sum << '\n';
// system("pause");
if(sum >= cap[v])
hi[v] = j;
else
lo[v] = j + 1;
if(lo[v] < hi[v])
qu[(lo[v]+hi[v])>>1].push_back(v);
}
}
for(int j = 0; j < k; j++){
if(l[j] <= r[j])
upd(1,0,m-1,l[j],r[j],-add[j]);
else
upd(1,0,m-1,l[j],m-1,-add[j]),
upd(1,0,m-1,0,r[j],-add[j]);
}
}
for(int i = 0; i < n; i++)
if(lo[i] == k)
puts("NIE");
else
printf("%d\n", lo[i]+1);
return 0;
}
Compilation message
met.cpp: In function 'int main()':
met.cpp:75:52: warning: format '%lld' expects argument of type 'long long int*', but argument 2 has type 'int*' [-Wformat=]
scanf("%lld%lld%lld", l + i, r + i, add + i), --l[i], --r[i];
~~~~~ ^
met.cpp:75:52: warning: format '%lld' expects argument of type 'long long int*', but argument 3 has type 'int*' [-Wformat=]
met.cpp:75:52: warning: format '%lld' expects argument of type 'long long int*', but argument 4 has type 'int*' [-Wformat=]
met.cpp:63:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &n, &m);
~~~~~^~~~~~~~~~~~~~~~
met.cpp:66:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", a + i); --a[i];
~~~~~^~~~~~~~~~~~~
met.cpp:71:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", cap + i);
~~~~~^~~~~~~~~~~~~~~
met.cpp:72:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &k);
~~~~~^~~~~~~~~~
met.cpp:75:61: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld%lld", l + i, r + i, add + i), --l[i], --r[i];
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1508 ms |
66560 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
472 ms |
66560 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
390 ms |
66560 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
6059 ms |
66560 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
6098 ms |
66560 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
6097 ms |
66560 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
6015 ms |
66560 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
6028 ms |
66560 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
