| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1049240 |
2024-08-08T15:23:03 Z |
Newtonabc |
Meteors (POI11_met) |
C++14 |
|
2637 ms |
48188 KB |
#include<bits/stdc++.h>
using namespace std;
const int N=3e5+10;
const int M=3e5+5;
int o[N],al[N],ar[N],mid[N],l[N],r[N],s[N];
long long p[N],a[N],fw[N];
vector<int> ask[N];
vector<int> own[N];
void update(int idx,long long val){
if(idx==0) return;
while(idx<=M){
fw[idx]+=val;
idx+=idx & -idx;
}
}
long long read(int idx){
long long sum=0;
while(idx>0){
sum+=fw[idx];
idx-=idx & -idx;
}
return sum;
}
int main(){
int n,m,k;
cin>>n >>m;
for(int i=1;i<=m;i++) cin>>o[i],own[o[i]].push_back(i);
for(int i=1;i<=n;i++) cin>>p[i];
cin>>k;
for(int i=1;i<=k;i++) cin>>al[i] >>ar[i] >>a[i];
for(int i=1;i<=n;i++) l[i]=1,r[i]=k;
while(true){
bool up=false;
for(int i=1;i<=n;i++) mid[i]=(l[i]+r[i])/2,ask[mid[i]].push_back(i);
for(int i=0;i<=M;i++) fw[i]=0;
for(int i=1;i<=k;i++){
if(al[i]<=ar[i]) update(al[i],a[i]),update(ar[i]+1,-1*a[i]);
else update(al[i],a[i]),update(m+1,-1*a[i]),update(1,a[i]),update(ar[i]+1,-1*a[i]);
for(int j=0;j<ask[i].size();j++){
int u=ask[i][j];
long long sum=0;
for(int x=0;x<own[u].size();x++){
sum+=read(own[u][x]);
}
if(sum>=p[u]){
if(r[u]!=mid[u]) up=true;
r[u]=mid[u];
}
else{
if(l[u]!=mid[u]+1) up=true;
l[u]=mid[u]+1;
}
}
}
if(!up) break;
}
for(int i=0;i<=M;i++) fw[i]=0;
for(int i=1;i<=k;i++){
if(al[i]<=ar[i]) update(al[i],a[i]),update(ar[i]+1,-1*a[i]);
else update(al[i],a[i]),update(m+1,-1*a[i]),update(1,a[i]),update(ar[i]+1,-1*a[i]);
for(int j=0;j<ask[i].size();j++){
int u=ask[i][j];
long long sum=0;
for(int x=0;x<own[u].size();x++){
sum+=read(own[u][x]);
}
s[u]=sum;
}
}
for(int i=1;i<=n;i++){
if(s[i]<p[i]) cout<<"NIE";
else cout<<r[i];
cout<<"\n";
}
}
Compilation message
met.cpp: In function 'int main()':
met.cpp:42:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
42 | for(int j=0;j<ask[i].size();j++){
| ~^~~~~~~~~~~~~~
met.cpp:45:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
45 | for(int x=0;x<own[u].size();x++){
| ~^~~~~~~~~~~~~~
met.cpp:64:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
64 | for(int j=0;j<ask[i].size();j++){
| ~^~~~~~~~~~~~~~
met.cpp:67:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
67 | for(int x=0;x<own[u].size();x++){
| ~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
27228 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
27228 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
131 ms |
30760 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
204 ms |
31512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
157 ms |
31056 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
196 ms |
20884 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2637 ms |
48188 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2298 ms |
47028 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
