| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 605630 |
2022-07-25T20:15:40 Z |
1ne |
Meteors (POI11_met) |
C++14 |
|
3429 ms |
40100 KB |
#include <bits/stdc++.h>
using namespace std;
struct node{
long long l,r,v;
};
struct dataa{
long long v = 0,lazy =0;
void add(long long left,long long right,long long val){
v+=val;
lazy+=val;
}
};
struct Segment_Tree{
vector<dataa>tree;
int m;
void init(long long n){
tree.resize(2*n - 1);
m = n - 1;
}
dataa combine(dataa& left,dataa& right){
dataa res;
res.v = left.v + right.v;
return res;
}
void push(long long node,long long left,long long right){
long long mid = (left + right)>>1;
long long z = node + ((mid - left + 1)<<1);
if (tree[node].lazy!=0){
tree[node + 1].add(left,mid,tree[node].lazy);
tree[z].add(mid + 1,right,tree[node].lazy);
tree[node].lazy = 0;
}
}
long long query(long long node,long long left,long long right,long long qleft,long long qright){
if (qright<left|| qleft > right)return 0;
if (qleft<=left && qright>=right){
return tree[node].v;
}
push(node,left,right);
long long mid = (left + right)>>1;
long long z = node + ((mid - left + 1)<<1);
long long ans = 0;
if (qleft<=mid){
ans+=query(node + 1,left,mid,qleft,qright);
}
if (qright > mid){
ans+=query(z,mid + 1,right,qleft,qright);
}
return ans;
}
void update(long long node,long long left,long long right,long long uleft,long long uright,long long v){
if (left > uright || right < uleft) return;
if (uleft <= left && right <=uright){
tree[node].add(left,right,v);
return;
}
push(node,left,right);
long long mid = (left + right)>>1;
long long z = node + ((mid - left + 1)<<1);
if (uleft<=mid){
update(node + 1,left,mid,uleft,uright,v);
}
if (uright > mid){
update(z,mid + 1,right,uleft,uright,v);
}
tree[node] = combine(tree[node + 1],tree[z]);
}
long long query(int qleft,int& qright){
return query(0,0,m,qleft,qright);
}
void update(int uleft,int uright,long long v){
update(0,0,m,uleft,uright,v);
}
};
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int n,m;cin>>n>>m;
vector<vector<int>>arr(n);
for (int i = 0;i<m;++i){
int x;cin>>x;
arr[x - 1].push_back(i);
}
vector<long long>brr(n);
for (int i = 0;i<n;++i)cin>>brr[i];
int k;cin>>k;
vector<node>edge(k);
for (int i = 0;i<k;++i){
cin>>edge[i].l>>edge[i].r>>edge[i].v;
edge[i].l--;
edge[i].r--;
}
vector<int>order(n);
iota(order.begin(),order.end(),0);
int pos = -1;
vector<int>ans(n);
Segment_Tree st;
st.init(m);
function<void(int,int,vector<int>&)>solve = [&](int left,int right,vector<int>&temp){
if (left == right){
for (auto x:temp){
ans[x] = left;
}
return;
}
int mid = (left + right)>>1;
if (pos > mid){
for (int i = mid + 1;i<=pos;++i){
if (edge[i].l<=edge[i].r){
st.update(edge[i].l,edge[i].r,-edge[i].v);
}
else{
st.update(edge[i].l,m - 1,-edge[i].v);
st.update(0,edge[i].r,-edge[i].v);
}
}
pos = mid;
}
else{
for (int i = pos + 1;i<=mid;++i){
if (edge[i].l<=edge[i].r){
st.update(edge[i].l,edge[i].r,edge[i].v);
}
else{
st.update(edge[i].l,m - 1,edge[i].v);
st.update(0,edge[i].r,edge[i].v);
}
}
pos = mid;
}
vector<int>f,s;
for (auto x:temp){
long long sum = 0;
for (auto y:arr[x]){
sum+=st.query(y,y);
if (sum >=brr[x])break;
}
//cout<<x.index<<" "<<mid<<" "<<k<<'\n';
if (sum>=brr[x]){
f.push_back(x);
}
else s.push_back(x);
}
if (!f.empty()){
solve(left,mid,f);
}
if (!s.empty()){
solve(mid + 1,right,s);
}
};
solve(0,k,order);
for (auto x:ans){
x++;
if (x > k)cout<<"NIE\n";
else cout<<x<<'\n';
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
340 KB |
Output is correct |
| 2 |
Correct |
2 ms |
340 KB |
Output is correct |
| 3 |
Correct |
3 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
340 KB |
Output is correct |
| 2 |
Correct |
2 ms |
340 KB |
Output is correct |
| 3 |
Correct |
4 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
106 ms |
3860 KB |
Output is correct |
| 2 |
Correct |
282 ms |
6168 KB |
Output is correct |
| 3 |
Correct |
315 ms |
4356 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
262 ms |
3948 KB |
Output is correct |
| 2 |
Correct |
261 ms |
3980 KB |
Output is correct |
| 3 |
Correct |
204 ms |
5712 KB |
Output is correct |
| 4 |
Correct |
75 ms |
3676 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
138 ms |
3840 KB |
Output is correct |
| 2 |
Correct |
225 ms |
5964 KB |
Output is correct |
| 3 |
Correct |
44 ms |
1492 KB |
Output is correct |
| 4 |
Correct |
264 ms |
4640 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
116 ms |
3388 KB |
Output is correct |
| 2 |
Correct |
246 ms |
4000 KB |
Output is correct |
| 3 |
Correct |
178 ms |
3488 KB |
Output is correct |
| 4 |
Correct |
294 ms |
5360 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1882 ms |
29312 KB |
Output is correct |
| 2 |
Correct |
240 ms |
18076 KB |
Output is correct |
| 3 |
Correct |
279 ms |
6228 KB |
Output is correct |
| 4 |
Correct |
3429 ms |
33292 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1637 ms |
27180 KB |
Output is correct |
| 2 |
Correct |
364 ms |
18024 KB |
Output is correct |
| 3 |
Correct |
96 ms |
5040 KB |
Output is correct |
| 4 |
Correct |
3089 ms |
40100 KB |
Output is correct |
