| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 752210 |
2023-06-02T13:44:06 Z |
salmon |
Meteors (POI11_met) |
C++14 |
|
371 ms |
65536 KB |
//meteors
#include <bits/stdc++.h>
using namespace std;
vector<int> st;
vector<int> l;
vector<int> r;
vector<int> place[300100];
int N,M,h;
int it;
int k;
int root[300100];
int g[300100];
int con;
void update(int i, int s, int e, int S, int E, int c, int k){
if(S <= E){
if(S <= s && e <= E){
if(con - st[c] < k){
st.push_back(con);
}
else{
st.push_back(st[c] + k);
}
l.push_back(l[c]);
r.push_back(r[c]);
it++;
return;
}
st.push_back(st[c]);
l.push_back(0);
r.push_back(0);
it++;
int m = (s + e)/2;
int lef = l[c];
int righ = r[c];
if(S <= m){
lef = it;
update(it, s, m, S, E, l[c], k);
}
if(E > m){
righ = it;
update(it,m + 1,e, S, E,r[c],k);
}
l[i] = lef;
r[i] = righ;
return;
}
else{
if(S <= s || e <= E){
if(con - st[c] < k){
st.push_back(con);
}
else{
st.push_back(st[c] + k);
}
l.push_back(l[c]);
r.push_back(r[c]);
it++;
return;
}
st.push_back(st[c]);
l.push_back(0);
r.push_back(0);
it++;
int m = (s + e)/2;
int lef = l[c];
int righ = r[c];
if(S <= m || s <= E){
lef = it;
update(it, s, m, S, E, l[c], k);
}
if(m < E || S <= e){
righ = it;
update(it,m + 1,e, S, E,r[c],k);
}
l[i] = lef;
r[i] = righ;
return;
}
}
int query(int i, int s, int e, int in){
if(s == e){
return st[i];
}
int ans;
if(in <= (s+e)/2){
ans = query(l[i], s, (s+e)/2,in);
}
else{
ans = query(r[i],(s+e)/2+1,e,in);
}
if(con - st[i] < ans){
return con;
}
else{
return st[i] + ans;
}
}
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]);
}
it = 0;
st.push_back(0);
l.push_back(0);
r.push_back(0);
it++;
scanf(" %d",&k);
root[0] = 0;
for(int i = 1; i <= k ; i++){
int s,e,a;
scanf(" %d",&s);
scanf(" %d",&e);
scanf(" %d",&a);
root[i] = it;
update(it, 1, M, s, e, root[i - 1], a);
}
for(int i = 1; i <= N; i++){
int s = 1;
int e = k + 1;
int m;
while(s != e){
m = (s+e)/2;
long long int some = 0;
for(int j : place[i]){
some += query(root[m],1,M,j);
}
if(some >= g[i]){
e = m;
}
else{
s = m + 1;
}
}
if(s == k + 1){
printf("NIE\n");
}
else{
printf("%d\n",s);
}
}
/*for(int j = 0; j <= k; j++){
for(int i = 1; i <= M; i++){
printf("%lld ",query(root[j],1,M,i));
}
printf("\n");
}*/
}
Compilation message
met.cpp: In function 'int main()':
met.cpp:118:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
118 | scanf(" %d",&N);
| ~~~~~^~~~~~~~~~
met.cpp:119:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
119 | scanf(" %d",&M);
| ~~~~~^~~~~~~~~~
met.cpp:122:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
122 | scanf(" %d",&h);
| ~~~~~^~~~~~~~~~
met.cpp:127:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
127 | scanf(" %d",&g[i]);
| ~~~~~^~~~~~~~~~~~~
met.cpp:136:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
136 | scanf(" %d",&k);
| ~~~~~^~~~~~~~~~
met.cpp:143:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
143 | scanf(" %d",&s);
| ~~~~~^~~~~~~~~~
met.cpp:144:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
144 | scanf(" %d",&e);
| ~~~~~^~~~~~~~~~
met.cpp:145:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
145 | scanf(" %d",&a);
| ~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
7764 KB |
Output is correct |
| 2 |
Correct |
5 ms |
7764 KB |
Output is correct |
| 3 |
Correct |
6 ms |
7764 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
7764 KB |
Output is correct |
| 2 |
Correct |
6 ms |
7764 KB |
Output is correct |
| 3 |
Correct |
7 ms |
7868 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
152 ms |
31960 KB |
Output is correct |
| 2 |
Correct |
251 ms |
41192 KB |
Output is correct |
| 3 |
Correct |
371 ms |
32144 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
229 ms |
32104 KB |
Output is correct |
| 2 |
Correct |
197 ms |
32100 KB |
Output is correct |
| 3 |
Correct |
220 ms |
41368 KB |
Output is correct |
| 4 |
Correct |
59 ms |
10296 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
120 ms |
24544 KB |
Output is correct |
| 2 |
Correct |
132 ms |
29804 KB |
Output is correct |
| 3 |
Correct |
51 ms |
24184 KB |
Output is correct |
| 4 |
Correct |
202 ms |
32272 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
220 ms |
40836 KB |
Output is correct |
| 2 |
Correct |
229 ms |
41128 KB |
Output is correct |
| 3 |
Correct |
157 ms |
32096 KB |
Output is correct |
| 4 |
Correct |
222 ms |
33164 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
265 ms |
65536 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
257 ms |
65536 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
