# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
40459 |
2018-02-01T19:48:39 Z |
IvanC |
Meteors (POI11_met) |
C++14 |
|
6000 ms |
48592 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct pergunta{
int ini,fim,meio,resp,id;
pergunta(int _ini = 0,int _fim = 0){
ini = _ini;
fim = _fim;
meio = -1;
resp = -1;
}
};
const int MAXN = 300010;
vector<int> estados[MAXN];
vector<pergunta> P;
ll seg[4*MAXN],lazy[4*MAXN];
int N,M,K,li[MAXN],ri[MAXN],ai[MAXN],qtd[MAXN],maximom;
vector<int> bucket[MAXN];
inline void propagate(int pos,int left,int right){
seg[pos] += lazy[pos];
if(left != right){
lazy[2*pos] += lazy[pos];
lazy[2*pos+1] += lazy[pos];
}
lazy[pos] = 0;
}
void build(int pos,int left,int right){
seg[pos] = lazy[pos] = 0;
if(left == right) return;
int mid = (left+right)/2;
build(2*pos,left,mid);
build(2*pos+1,mid+1,right);
}
void update(int pos,int left,int right,int i,int j,ll val){
propagate(pos,left,right);
if(left > right || left > j || right < i) return;
if(left >= i && right <= j){
lazy[pos] += val;
propagate(pos,left,right);
return;
}
int mid = (left+right)/2;
update(2*pos,left,mid,i,j,val);
update(2*pos+1,mid+1,right,i,j,val);
}
inline ll query(int pos,int left,int right,int x){
while(left != right){
propagate(pos,left,right);
int mid = (left+right)/2;
if(x <= mid){
right = mid;
pos = 2*pos;
}
else{
left = mid + 1;
pos = 2*pos + 1;
}
}
propagate(pos,left,right);
return seg[pos];
}
void do_update(int i){
if(li[i] <= ri[i]){
update(1,1,M,li[i],ri[i],ai[i]);
}
else{
update(1,1,M,li[i],M,ai[i]);
update(1,1,M,1,ri[i],ai[i]);
}
}
void checa(int i){
ll tot = qtd[i];
for(int j : estados[i]){
tot -= query(1,1,M,j);
if(tot <= 0) break;
}
if(tot <= 0){
P[i].resp = P[i].meio;
P[i].fim = P[i].meio - 1;
}
else{
P[i].ini = P[i].meio + 1;
}
}
int main(){
pergunta dummy(0,0);
P.push_back(dummy);
scanf("%d %d",&N,&M);
for(int i = 1;i<=M;i++){
int x;
scanf("%d",&x);
estados[x].push_back(i);
}
for(int i = 1;i<=N;i++) scanf("%d",&qtd[i]);
scanf("%d",&K);
for(int i = 1;i<=N;i++){
pergunta davez(1,K);
P.push_back(davez);
}
for(int i = 1;i<=K;i++){
scanf("%d %d %d",&li[i],&ri[i],&ai[i]);
}
int limite = ceil(log(K)/log(2)) + 1;
for(int iteracao = 1;iteracao<=limite;iteracao++){
build(1,1,M);
maximom = 0;
for(int i = 1;i<=N;i++){
if(P[i].ini > P[i].fim){
continue;
}
P[i].meio = (P[i].ini + P[i].fim)/2;
maximom = max(P[i].meio,maximom);
bucket[P[i].meio].push_back(i);
}
for(int atualizacao = 1;atualizacao<=maximom;atualizacao++){
do_update(atualizacao);
if(bucket[atualizacao].empty()) continue;
while(!bucket[atualizacao].empty()){
int i = bucket[atualizacao].back();
bucket[atualizacao].pop_back();
checa(i);
}
}
}
for(int i = 1;i<=N;i++){
if(P[i].resp == -1) printf("NIE \n");
else printf("%d\n",P[i].resp);
}
return 0;
}
Compilation message
met.cpp: In function 'int main()':
met.cpp:88:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&N,&M);
^
met.cpp:91:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&x);
^
met.cpp:94:45: 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("%d",&qtd[i]);
^
met.cpp:95:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&K);
^
met.cpp:101:41: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d",&li[i],&ri[i],&ai[i]);
^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
14456 KB |
Output is correct |
2 |
Correct |
16 ms |
14564 KB |
Output is correct |
3 |
Correct |
17 ms |
14760 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
14760 KB |
Output is correct |
2 |
Correct |
17 ms |
14760 KB |
Output is correct |
3 |
Correct |
17 ms |
14760 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
464 ms |
18396 KB |
Output is correct |
2 |
Correct |
612 ms |
20496 KB |
Output is correct |
3 |
Correct |
683 ms |
20496 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
550 ms |
20496 KB |
Output is correct |
2 |
Correct |
548 ms |
20496 KB |
Output is correct |
3 |
Correct |
578 ms |
20528 KB |
Output is correct |
4 |
Correct |
132 ms |
20528 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
300 ms |
20528 KB |
Output is correct |
2 |
Correct |
486 ms |
21136 KB |
Output is correct |
3 |
Correct |
110 ms |
21136 KB |
Output is correct |
4 |
Correct |
557 ms |
21136 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
200 ms |
21136 KB |
Output is correct |
2 |
Correct |
508 ms |
21136 KB |
Output is correct |
3 |
Correct |
518 ms |
21136 KB |
Output is correct |
4 |
Correct |
632 ms |
22036 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
6050 ms |
48592 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
6073 ms |
48592 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |