| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 102730 |
2019-03-27T09:44:50 Z |
bakpark |
Meteors (POI11_met) |
C++14 |
|
4161 ms |
66560 KB |
#include <cstdio>
#include <algorithm>
#include <memory.h>
#include <vector>
using namespace std;
#define ll long long
struct quer{
int l,r;
ll val;
};
int N,M,Q;
ll tree[2000000];
ll need[300005];
quer q[300005];
vector<int> arr[300005];
vector<int> bs[300005];
int L[300005],R[300005],answ[300005];
int MAX=1;
void push(int x,int l,int r,int LL,int RR,ll val){
if(r<LL||RR<l) return;
if(LL<=l&&r<=RR){
tree[x]+=val;
return;
}
int m = (l+r)>>1;
push(x<<1,l,m,LL,RR,val);
push((x<<1)+1,m+1,r,LL,RR,val);
}
ll get(int pos){
ll sum = 0;
int x = MAX-1+pos;
while(x>0){
sum+=tree[x];
x = x>>1;
}
return sum;
}
int main(){
scanf("%d %d",&N,&M);
while(MAX<M){
MAX = MAX<<1;
}
for(int i=1;i<=M;i++){
int tmp;
scanf("%d",&tmp);
arr[tmp].push_back(i);
}
for(int i=1;i<=N;i++) scanf("%lld",&need[i]);
scanf("%d",&Q);
for(int i=1;i<=Q;i++) {
scanf("%d %d %lld",&q[i].l,&q[i].r,&q[i].val);
}
for(int i=1;i<=N;i++){
L[i] = 1;
R[i] = Q;
answ[i] = -1;
bs[(Q+1)>>1].push_back(i);
}
bool flag = true;
while(flag){
memset(tree,0,sizeof(tree));
flag = false;
for(int i=1;i<=Q;i++){
int l = q[i].l,r = q[i].r;
ll val = q[i].val;
if(l<=r){
push(1,1,MAX,l,r,val);
}
else{
push(1,1,MAX,l,M,val);
push(1,1,MAX,1,r,val);
}
for(int ver:bs[i]){
ll sum = 0;
bool done = false;
for(int pos:arr[ver]){
sum+=get(pos);
if(sum>=need[ver]){
R[ver] = i-1;
answ[ver] = i;
done = true;
break;
}
}
if(!done) L[ver] = i+1;
if(L[ver]<=R[ver]){
int m = (L[ver]+R[ver])>>1;
bs[m].push_back(ver);
if(m<i) flag = true;
}
}
bs[i].clear();
}
}
for(int i=1;i<=N;i++){
if(answ[i]==-1) printf("NIE\n");
else printf("%d\n",answ[i]);
}
}
Compilation message
met.cpp: In function 'int main()':
met.cpp:42: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:48:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&tmp);
~~~~~^~~~~~~~~~~
met.cpp:51:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i=1;i<=N;i++) scanf("%lld",&need[i]);
~~~~~^~~~~~~~~~~~~~~~~
met.cpp:52:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&Q);
~~~~~^~~~~~~~~
met.cpp:54:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %lld",&q[i].l,&q[i].r,&q[i].val);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
47 ms |
30200 KB |
Output is correct |
| 2 |
Correct |
45 ms |
30200 KB |
Output is correct |
| 3 |
Correct |
46 ms |
30200 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
55 ms |
30208 KB |
Output is correct |
| 2 |
Correct |
49 ms |
30200 KB |
Output is correct |
| 3 |
Correct |
47 ms |
30200 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
327 ms |
31608 KB |
Output is correct |
| 2 |
Correct |
426 ms |
33912 KB |
Output is correct |
| 3 |
Correct |
438 ms |
33528 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
425 ms |
32832 KB |
Output is correct |
| 2 |
Correct |
407 ms |
32760 KB |
Output is correct |
| 3 |
Correct |
517 ms |
34040 KB |
Output is correct |
| 4 |
Correct |
144 ms |
31992 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
197 ms |
32260 KB |
Output is correct |
| 2 |
Correct |
354 ms |
34472 KB |
Output is correct |
| 3 |
Correct |
220 ms |
31096 KB |
Output is correct |
| 4 |
Correct |
411 ms |
33912 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
461 ms |
31480 KB |
Output is correct |
| 2 |
Correct |
395 ms |
32888 KB |
Output is correct |
| 3 |
Correct |
329 ms |
31716 KB |
Output is correct |
| 4 |
Correct |
473 ms |
35320 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2683 ms |
49020 KB |
Output is correct |
| 2 |
Correct |
1530 ms |
36080 KB |
Output is correct |
| 3 |
Correct |
841 ms |
36728 KB |
Output is correct |
| 4 |
Runtime error |
4161 ms |
66560 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2970 ms |
47756 KB |
Output is correct |
| 2 |
Correct |
1027 ms |
36308 KB |
Output is correct |
| 3 |
Correct |
884 ms |
36960 KB |
Output is correct |
| 4 |
Runtime error |
3316 ms |
66560 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
