| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1049301 |
2024-08-08T16:08:41 Z |
Newtonabc |
Meteors (POI11_met) |
C++14 |
|
1296 ms |
65536 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];
long long p[N],a[N],fw[N],s[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(){
ios_base::sync_with_stdio(0);
cin.tie(0);
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<=k;i++) ask[i].clear();
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>1e9) sum=1e9+1;
}
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 i=1;i<=n;i++){
long long sum=0;
for(int j=0;j<own[i].size();j++){
sum+=read(own[i][j]);
if(sum>1e9) sum=1e9+1;
}
s[i]=sum;
}
for(int i=1;i<=n;i++){
if(s[i]<p[i]) cout<<"NIE";
else cout<<l[i];
cout<<"\n";
}
}
Compilation message
met.cpp: In function 'int main()':
met.cpp:45:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
45 | for(int j=0;j<ask[i].size();j++){
| ~^~~~~~~~~~~~~~
met.cpp:48:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
48 | for(int x=0;x<own[u].size();x++){
| ~^~~~~~~~~~~~~~
met.cpp:71:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
71 | for(int j=0;j<own[i].size();j++){
| ~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
29276 KB |
Output is correct |
| 2 |
Correct |
5 ms |
29276 KB |
Output is correct |
| 3 |
Correct |
5 ms |
29276 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
29276 KB |
Output is correct |
| 2 |
Correct |
5 ms |
29276 KB |
Output is correct |
| 3 |
Correct |
6 ms |
29276 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
81 ms |
30288 KB |
Output is correct |
| 2 |
Correct |
177 ms |
32080 KB |
Output is correct |
| 3 |
Correct |
107 ms |
31828 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
139 ms |
31316 KB |
Output is correct |
| 2 |
Correct |
140 ms |
31140 KB |
Output is correct |
| 3 |
Correct |
181 ms |
32084 KB |
Output is correct |
| 4 |
Correct |
22 ms |
31068 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
113 ms |
30736 KB |
Output is correct |
| 2 |
Correct |
179 ms |
32596 KB |
Output is correct |
| 3 |
Correct |
127 ms |
29272 KB |
Output is correct |
| 4 |
Correct |
112 ms |
32132 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
178 ms |
29788 KB |
Output is correct |
| 2 |
Correct |
176 ms |
31124 KB |
Output is correct |
| 3 |
Correct |
88 ms |
30032 KB |
Output is correct |
| 4 |
Correct |
150 ms |
33248 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
963 ms |
43176 KB |
Output is correct |
| 2 |
Correct |
711 ms |
32284 KB |
Output is correct |
| 3 |
Correct |
697 ms |
32080 KB |
Output is correct |
| 4 |
Correct |
1195 ms |
65536 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
955 ms |
41996 KB |
Output is correct |
| 2 |
Correct |
707 ms |
32216 KB |
Output is correct |
| 3 |
Correct |
568 ms |
32672 KB |
Output is correct |
| 4 |
Correct |
1296 ms |
65536 KB |
Output is correct |
