이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int const N=3e5+5;
int const mod=1e9+7;
int low[N],high[N];
int target[N];
int owner[N];
vector<int> property[N];
int n,m;
int shower[N][3];
vector<int> query_on_mid[N];
ll seg[4*N];
ll lazy[4*N];
void push(int v,int s,int e)
{
int lc=v*2,rc=lc+1,mid=(s+e)/2;
seg[lc]+=lazy[v]*(mid-s),seg[rc]+=lazy[v]*(e-mid);
lazy[lc]+=lazy[v],lazy[rc]+=lazy[v];
lazy[v]=0;
}
void update(int node,int l,int r,int val,int s=0,int e=m){
if(e<=l || r<=s)
return;
if(l<=s && e<=r){
lazy[node]+=val;
seg[node]+=val*(e-s);
return;
}
int mid=(s+e)/2;
push(node,s,e);
update(node*2,l,r,val,s,mid);
update(node*2+1,l,r,val,mid,e);
seg[node]=seg[node*2]+seg[node*2+1];
}
ll query(int node,int l,int r,int s=0,int e=m){
if(e<=l || r<=s)
return 0;
if(l<=s && e<=r)
return seg[node];
int mid=(s+e)/2;
push(node,s,e);
return query(node*2,l,r,s,mid)+query(node*2+1,l,r,mid,e);
}
int main(){
cin>>n>>m;
for (int i = 0; i < m; ++i){
cin>>owner[i];
owner[i]--;
property[owner[i]].push_back(i);
}
for(int i=0;i<n;i++)
cin>>target[i];
int q;
cin>>q;
for (int i = 0; i < q; ++i){
cin>>shower[i][0]>>shower[i][1]>>shower[i][2];
shower[i][0]--;
}
for(int i=0;i<n;i++){
high[i]=q;
low[i]=-1;
}
for(int lg=0;lg<20;lg++){
for(int i=0;i<q;i++)
query_on_mid[i].clear();
for(int i=0;i<n;i++){
int mid=(high[i]+low[i])/2;
query_on_mid[mid].push_back(i);
}
for(int i=0;i<4*m;i++)//segment tree reset
seg[i]=lazy[i]=0;
for(int i=0;i<q;i++){
if(shower[i][0]>shower[i][1]){
update(1,shower[i][0],m,shower[i][2]);
update(1,0,shower[i][1],shower[i][2]);
}
else
update(1,shower[i][0],shower[i][1],shower[i][2]);
for(auto st:query_on_mid[i]){
ll sm=0;
for(auto p:property[st])
sm+=query(1,p,p+1);
if(sm>=target[st])
high[st]=i;
else
low[st]=i;
}
}
}
for(int i=0;i<n;i++){
if(high[i]==q)
cout<<"NIE"<<endl;
else
cout<<high[i]+1<<endl;
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |