| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 100128 |
2019-03-09T10:53:48 Z |
KLPP |
Meteors (POI11_met) |
C++14 |
|
256 ms |
66560 KB |
#include<bits/stdc++.h>
using namespace std;
typedef long long int lld;
int N,M,Q;
vector<int> stations[300005];
lld require[300005];
struct node{
node *l,*r;
int x,y;
lld sum;
};
node *versions[600005];
int version[300005];
void Start(node *n){
//cout<<n->x<<" "<<n->y<<endl;
n->sum=0;
if(n->x==n->y){
return;
}
n->l=new node();
n->r=new node();
n->l->x=n->x;
n->r->y=n->y;
int mid=(n->x+n->y)/2;
n->l->y=mid;
n->r->x=mid+1;
//cout<<n->l->x<<" "<<n->l->y<<endl;
Start(n->l);
Start(n->r);
}
void Atualizar(node *n, node *m, int pos, lld val){
if(m->x==m->y){
m->sum=n->sum;
m->sum+=val;
return;
}
int mid=(m->x+m->y)/2;
if(pos<=mid){
m->r=n->r;
m->l=new node();
m->l->x=m->x;
m->l->y=mid;
Atualizar(n->l,m->l,pos,val);
m->sum=m->r->sum+m->l->sum;
}else{
m->l=n->l;
m->r=new node();
m->r->x=mid+1;
m->r->y=m->y;
Atualizar(n->r,m->r,pos,val);
m->sum=m->r->sum+m->l->sum;
}
}
lld query(node *n, int x, int y){
if(n->y<x || y<n->x)return 0;
if(x<=n->x && n->y<=y)return n->sum;
return query(n->l,x,y)+query(n->r,x,y);
}
int main(){
scanf("%d %d",&N,&M);
for(int i=0;i<M;i++){
int x;
scanf("%d",&x);
x--;
stations[x].push_back(i);
}
for(int i=0;i<N;i++){
scanf("%lld",require+i);
}
scanf("%d",&Q);
for(int i=0;i<=2*Q;i++)versions[i]=new node();
for(int i=0;i<=2*Q;i++){
versions[i]->x=0;
versions[i]->y=M;
}
Start(versions[0]);
int cnt=0;
lld add[Q+1];
add[0]=0;
for(int i=0;i<Q;i++){
int l,r;
lld a;
scanf("%d %d %lld",&l,&r,&a);
l--;r--;
add[i+1]=add[i];
if(l<=r){
Atualizar(versions[cnt],versions[cnt+1],l,a);
cnt++;
//version[cnt]=i;
//cout<<l<<" "<<r<<endl;
Atualizar(versions[cnt],versions[cnt+1],r+1,-a);
cnt++;
//version[cnt]=i;
//cout<<l<<" "<<r<<endl;
}else{
Atualizar(versions[cnt],versions[cnt+1],l,a);
cnt++;
Atualizar(versions[cnt],versions[cnt+1],r+1,-a);
cnt++;
add[i+1]+=a;
}
version[i]=cnt;
//cout<<add[i+1]<<endl;
//cout<<cnt<<endl;
}
/*for(int i=0;i<Q;i++){
cout<<query(versions[version[i]],0,4)+add[i+1]<<" "<<query(versions[version[i]],0,3)+add[i+1]<<endl;
}*/
for(int i=0;i<N;i++){
int lo=-1;
int hi=Q;
/*for(int j=0;j<stations[i].size();j++){
cout<<stations[i][j]<<" ";
}cout<<endl;*/
while(hi-lo>1){
int mid=(hi+lo)/2;
//cout<<lo<<" "<<hi<<" "<<mid<<endl;
lld samples=0;
for(int j=0;j<stations[i].size();j++){
samples+=query(versions[version[mid]],0,stations[i][j])+add[mid+1];
}//cout<<samples<<" A "<<mid<<" "<<add[mid+1]<<endl;
if(samples>=require[i]){
hi=mid;
}else lo=mid;
}
if(hi<Q){
printf("%d\n",hi+1);
}else printf("NIE\n");
}
return 0;
}
Compilation message
met.cpp: In function 'int main()':
met.cpp:120:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<stations[i].size();j++){
~^~~~~~~~~~~~~~~~~~~
met.cpp:61:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&N,&M);
~~~~~^~~~~~~~~~~~~~~
met.cpp:64:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&x);
~~~~~^~~~~~~~~
met.cpp:69:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld",require+i);
~~~~~^~~~~~~~~~~~~~~~~~
met.cpp:71:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&Q);
~~~~~^~~~~~~~~
met.cpp:84:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %lld",&l,&r,&a);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
8576 KB |
Output is correct |
| 2 |
Correct |
11 ms |
8576 KB |
Output is correct |
| 3 |
Correct |
11 ms |
8576 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
8448 KB |
Output is correct |
| 2 |
Correct |
11 ms |
8448 KB |
Output is correct |
| 3 |
Correct |
10 ms |
8576 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
161 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 |
169 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 |
111 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 |
171 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 |
256 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 |
219 ms |
66560 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
