| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 748273 |
2023-05-26T03:08:18 Z |
jamezzz |
Meteors (POI11_met) |
C++17 |
|
874 ms |
30888 KB |
#include <bits/stdc++.h>
using namespace std;
#define sf scanf
#define pf printf
#define fi first
#define se second
#define INF 1023456789
#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;
ft[x]=min(ft[x],(ll)INF);
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:36:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
36 | sf("%d%d",&n,&m);
| ^
met.cpp:38:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
38 | sf("%d",&o);
| ^
met.cpp:41:25: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
41 | for(int i=1;i<=n;++i)sf("%d",&p[i]);
| ^
met.cpp:42:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
42 | sf("%d",&k);
| ^
met.cpp:44:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
44 | sf("%d%d%d",&l[i],&r[i],&a[i]);
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
9684 KB |
Output is correct |
| 2 |
Correct |
8 ms |
9812 KB |
Output is correct |
| 3 |
Correct |
7 ms |
9784 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
9684 KB |
Output is correct |
| 2 |
Correct |
6 ms |
9684 KB |
Output is correct |
| 3 |
Correct |
7 ms |
9812 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
63 ms |
11856 KB |
Output is correct |
| 2 |
Correct |
110 ms |
13928 KB |
Output is correct |
| 3 |
Correct |
90 ms |
13564 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
90 ms |
12208 KB |
Output is correct |
| 2 |
Correct |
101 ms |
13388 KB |
Output is correct |
| 3 |
Correct |
104 ms |
13808 KB |
Output is correct |
| 4 |
Correct |
30 ms |
11352 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
74 ms |
11980 KB |
Output is correct |
| 2 |
Correct |
87 ms |
14372 KB |
Output is correct |
| 3 |
Correct |
46 ms |
11972 KB |
Output is correct |
| 4 |
Correct |
89 ms |
13896 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
79 ms |
11688 KB |
Output is correct |
| 2 |
Correct |
92 ms |
13388 KB |
Output is correct |
| 3 |
Correct |
73 ms |
12836 KB |
Output is correct |
| 4 |
Correct |
105 ms |
14376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
824 ms |
27892 KB |
Output is correct |
| 2 |
Incorrect |
523 ms |
30888 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
874 ms |
27476 KB |
Output is correct |
| 2 |
Incorrect |
520 ms |
29380 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
