| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 418243 |
2021-06-05T08:40:03 Z |
jamezzz |
Meteors (POI11_met) |
C++17 |
|
1038 ms |
35828 KB |
#include <bits/stdc++.h>
using namespace std;
#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb emplace_back
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
typedef long long ll;
typedef vector<int> vi;
struct query{ int s,e;vi v; };
queue<query> q;
int n,m,o,p[300005],k,l[300005],r[300005],a[300005],ans[300005];
ll ft[300005];
vi s[300005];
void up(int x,int v){
while(x<=m)ft[x]+=v,x+=x&-x;
}
ll qry(int x){
ll res=0;
while(x)res+=ft[x],x-=x&-x;
return res;
}
int main(){
sf("%d%d",&n,&m);
for(int i=1;i<=m;++i){
sf("%d",&o);
s[o].pb(i);
}
for(int i=1;i<=n;++i)sf("%d",&p[i]);
sf("%d",&k);
for(int i=1;i<=k;++i){
sf("%d%d%d",&l[i],&r[i],&a[i]);
}
l[k+1]=1;r[k+1]=m;a[k+1]=1e9;
query x={1,k+1};
for(int i=1;i<=n;++i)x.v.pb(i);
q.push(x);
int pv=0;
while(!q.empty()){
query x={0,0};
swap(x,q.front());
q.pop();
if(x.s==x.e){
for(int i:x.v)ans[i]=x.s;
continue;
}
int md=(x.s+x.e)/2;
query nl={x.s,md},nr={md+1,x.e};
if(md<pv)memset(ft,0,sizeof ft),pv=0;
while(pv!=md){
++pv;
if(l[pv]<=r[pv]){
up(l[pv],a[pv]);
up(r[pv]+1,-a[pv]);
}
else{
up(1,a[pv]);
up(r[pv]+1,-a[pv]);
up(l[pv],a[pv]);
}
}
for(int i:x.v){
ll tot=0;
for(int j:s[i])tot+=qry(j);
if(tot>=p[i])nl.v.pb(i);
else nr.v.pb(i);
}
q.push(nl);q.push(nr);
}
for(int i=1;i<=n;++i){
if(ans[i]<=k)pf("%d\n",ans[i]);
else pf("NIE\n");
}
}
Compilation message
met.cpp: In function 'int main()':
met.cpp:31:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
31 | sf("%d%d",&n,&m);
| ^
met.cpp:33:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
33 | sf("%d",&o);
| ^
met.cpp:36:25: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
36 | for(int i=1;i<=n;++i)sf("%d",&p[i]);
| ^
met.cpp:37:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
37 | sf("%d",&k);
| ^
met.cpp:39:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
39 | sf("%d%d%d",&l[i],&r[i],&a[i]);
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
9676 KB |
Output is correct |
| 2 |
Correct |
7 ms |
9676 KB |
Output is correct |
| 3 |
Correct |
7 ms |
9804 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
9792 KB |
Output is correct |
| 2 |
Correct |
7 ms |
9700 KB |
Output is correct |
| 3 |
Correct |
8 ms |
9804 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
76 ms |
12616 KB |
Output is correct |
| 2 |
Correct |
119 ms |
13992 KB |
Output is correct |
| 3 |
Correct |
99 ms |
13620 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
100 ms |
13284 KB |
Output is correct |
| 2 |
Correct |
102 ms |
13256 KB |
Output is correct |
| 3 |
Correct |
119 ms |
13824 KB |
Output is correct |
| 4 |
Correct |
36 ms |
11304 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
83 ms |
12740 KB |
Output is correct |
| 2 |
Correct |
99 ms |
14200 KB |
Output is correct |
| 3 |
Correct |
50 ms |
12124 KB |
Output is correct |
| 4 |
Correct |
101 ms |
13760 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
97 ms |
12752 KB |
Output is correct |
| 2 |
Correct |
122 ms |
13460 KB |
Output is correct |
| 3 |
Correct |
90 ms |
12752 KB |
Output is correct |
| 4 |
Correct |
120 ms |
14316 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1006 ms |
35828 KB |
Output is correct |
| 2 |
Incorrect |
686 ms |
30908 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1038 ms |
35196 KB |
Output is correct |
| 2 |
Incorrect |
692 ms |
29500 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
