| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 752258 |
2023-06-02T15:23:54 Z |
salmon |
Meteors (POI11_met) |
C++14 |
|
2684 ms |
65536 KB |
//meteors
#include <bits/stdc++.h>
using namespace std;
long long int st[1200100];
vector<int> place[300100];
int N,M,h;
int k;
int g[300100];
vector<int> m[300100];
int s[300100];
int e[300100];
vector<vector<int>> days;
int ans[300100];
long long int con;
void build(int i, int s, int e){
if(s == e){
st[i] = 0;
return;
}
st[i] = 0;
build(i * 2,s,(s+e)/2);
build(i*2+1,(s+e)/2+1, e);
}
void update(int i, int s, int e, int S, int E, int k){
if(S <= s && e <= E){
st[i] = st[i] + k;
return;
}
int m = (s + e)/2;
if(S <= m){
update(i * 2, s, m,S,E,k);
}
if(m < E){
update(i*2+1,m+1,e,S,E,k);
}
}
long long int query(int i, int s, int e, int in){
if(s == e){
return st[i];
}
int m = (s + e)/2;
if(in <= m){
return min(con,st[i] + query(i*2, s, m, in));
}
else{
return min(con,st[i] + query(i * 2+1,m + 1, e, in));
}
}
int main(){
con = 1000000000;
scanf(" %d",&N);
scanf(" %d",&M);
for(int i = 1; i <= M; i++){
scanf(" %d",&h);
place[h].push_back(i);
}
for(int i = 1; i <= N; i++){
scanf(" %d",&g[i]);
}
scanf(" %d",&k);
for(int i = 1; i <= N; i++){
s[i] = 1;
e[i] = k + 1;
m[(k + 2)/2].push_back(i);
}
for(int i = 1; i <= k ; i++){
int s,e,a;
scanf(" %d",&s);
scanf(" %d",&e);
scanf(" %d",&a);
vector<int> v = {s,e,a};
days.push_back(v);
}
bool flag = true;
while(flag){
flag = false;
build(1,1,M);
for(int i = 1; i <= k; i++){
if(days[i-1][1] < days[i-1][0]){
update(1,1,M,1,days[i-1][1],days[i-1][2]);
update(1,1,M,days[i-1][0],M,days[i-1][2]);
}
else{
update(1,1,M,days[i-1][0],days[i-1][1],days[i-1][2]);
}
/*for(int i = 1; i <= M; i++){
printf("%lld ",query(1,1,M,i));
}
printf("\n");*/
for(int j : m[i]){
flag = true;
long long int some = 0;
for(int k : place[j]){
some = some + query(1,1,M,k);
}
if(some >= g[j]) e[j] = (s[j] + e[j])/2;
else s[j] = (s[j] + e[j])/2 + 1;
if(e[j] != s[j]) m[(s[j] + e[j])/2].push_back(j);
else ans[j] = s[j];
}
m[i].clear();
}
}
for(int i = 1; i <= N; i++){
if(ans[i] == k + 1){
printf("NIE\n");
}
else{
printf("%d\n",ans[i]);
}
}
}
Compilation message
met.cpp: In function 'int main()':
met.cpp:63:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
63 | scanf(" %d",&N);
| ~~~~~^~~~~~~~~~
met.cpp:64:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
64 | scanf(" %d",&M);
| ~~~~~^~~~~~~~~~
met.cpp:67:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
67 | scanf(" %d",&h);
| ~~~~~^~~~~~~~~~
met.cpp:72:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
72 | scanf(" %d",&g[i]);
| ~~~~~^~~~~~~~~~~~~
met.cpp:75:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
75 | scanf(" %d",&k);
| ~~~~~^~~~~~~~~~
met.cpp:86:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
86 | scanf(" %d",&s);
| ~~~~~^~~~~~~~~~
met.cpp:87:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
87 | scanf(" %d",&e);
| ~~~~~^~~~~~~~~~
met.cpp:88:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
88 | scanf(" %d",&a);
| ~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
14420 KB |
Output is correct |
| 2 |
Correct |
11 ms |
14676 KB |
Output is correct |
| 3 |
Correct |
10 ms |
14456 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
14420 KB |
Output is correct |
| 2 |
Correct |
11 ms |
14536 KB |
Output is correct |
| 3 |
Correct |
12 ms |
14548 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
300 ms |
18884 KB |
Output is correct |
| 2 |
Correct |
339 ms |
21036 KB |
Output is correct |
| 3 |
Correct |
335 ms |
20556 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
312 ms |
20144 KB |
Output is correct |
| 2 |
Correct |
307 ms |
20156 KB |
Output is correct |
| 3 |
Correct |
366 ms |
21084 KB |
Output is correct |
| 4 |
Correct |
82 ms |
17456 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
166 ms |
19512 KB |
Output is correct |
| 2 |
Correct |
201 ms |
21508 KB |
Output is correct |
| 3 |
Correct |
127 ms |
17408 KB |
Output is correct |
| 4 |
Correct |
307 ms |
20940 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
313 ms |
18528 KB |
Output is correct |
| 2 |
Correct |
304 ms |
20064 KB |
Output is correct |
| 3 |
Correct |
273 ms |
18800 KB |
Output is correct |
| 4 |
Correct |
336 ms |
22240 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2408 ms |
52716 KB |
Output is correct |
| 2 |
Correct |
1394 ms |
40256 KB |
Output is correct |
| 3 |
Correct |
692 ms |
30212 KB |
Output is correct |
| 4 |
Runtime error |
2354 ms |
65536 KB |
Execution killed with signal 9 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2684 ms |
51332 KB |
Output is correct |
| 2 |
Correct |
1192 ms |
40360 KB |
Output is correct |
| 3 |
Correct |
620 ms |
27372 KB |
Output is correct |
| 4 |
Runtime error |
2130 ms |
65536 KB |
Execution killed with signal 9 |
| 5 |
Halted |
0 ms |
0 KB |
- |
