#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
ll dp[300001],sl[300001],sr[300001],si[300001],mmax[100001],mmax_mi[100001],ans,ma;
map<pii,int> val;
vector<pii> vv,v,temp_val; //(index, height)
queue<pii> temp_col; //(height, index)
queue<pii> col[100001]; //(height, value)
set<int> cor_x;
queue<int> qx;
multiset<ll, greater<ll>> mo,le;
ll max_weights(int n, int m, vector<int> X, vector<int> Y, vector<int> W) {
for (int i=0; i<m; ++i) {
val[pii(X[i],Y[i])]=W[i];
vv.push_back(pii(X[i],Y[i]));
cor_x.insert(X[i]);
if (X[i]) v.push_back(pii(X[i]-1,Y[i]));
if (X[i]<n-1) v.push_back(pii(X[i]+1,Y[i]));
}
for (auto s : cor_x) qx.push(s);
sort(vv.begin(),vv.end());
for (auto s : vv) col[s.first].push(pii(s.second,val[pii(s.first,s.second)]));
sort(v.begin(),v.end());
int i=1,pre=-1;
for (auto s : v) {
int x=s.first, y=s.second;
if (x==pre) { //same x_cor
si[i]=si[i-1];
while (!col[x].empty() & y>=col[x].front().first) {
si[i]+=col[x].front().second;
col[x].pop();
}
sr[i]=sr[i-1]+val[pii(x+1,y)];
sl[i]=sl[i-1]+val[pii(x-1,y)];
} else { //new x_cor
/*
while (!col[x].empty() & y>=col[x].front().first) {
si[i]+=col[x].front().second;
col[x].pop();
}
sr[i]=val[pii(x+1,y)];
sl[i]=val[pii(x-1,y)];
//clear more, less, temp
mo.clear();
le.clear();
while (!temp_col.empty()) temp_col.pop();
for (auto h : temp_val) {
mo.insert(dp[h.first]);
temp_col.push(pii(h.second,h.first));
}
temp_val.clear();
//find max from all previous col (ma)
while (!qx.empty() && qx.front()<x-2) {
ma=max(ma,mmax[qx.front()]);
qx.pop();
}
if (qx.front()==x-2) ma=max(ma,mmax_mi[qx.front()]); */
}
//more to less
while (!temp_col.empty() && temp_col.front().first<y) {
int idx=temp_col.front().second;
temp_col.pop();
auto it=mo.find(dp[idx]);
mo.erase(it);
le.insert(dp[idx]-si[idx]-sr[idx]);
}
dp[i]=ma+sl[i]+sr[i];
if (!mo.empty()) dp[i]=max(dp[i],*(mo.begin())-si[i]+sr[i]);
if (!le.empty()) dp[i]=max(dp[i],*(le.begin())+sl[i]+sr[i]);
mmax_mi[x]=max(mmax_mi[x],dp[i]-sr[i]);
mmax[x]=max(mmax[x],dp[i]);
ans=max(ans,dp[i]);
temp_val.push_back(pii(i,y));
++i;
if (x!=pre) pre=x;
}
return ans;
}
Compilation message
fish.cpp: In function 'll max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:40:39: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
40 | while (!col[x].empty() & y>=col[x].front().first) {
| ~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
151 ms |
84672 KB |
1st lines differ - on the 1st token, expected: '40313272768926', found: '40313049006569' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
49 ms |
67628 KB |
1st lines differ - on the 1st token, expected: '2', found: '0' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
42 ms |
67616 KB |
1st lines differ - on the 1st token, expected: '10082010', found: '0' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
42 ms |
67640 KB |
1st lines differ - on the 1st token, expected: '3', found: '1' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
42 ms |
67640 KB |
1st lines differ - on the 1st token, expected: '3', found: '1' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
42 ms |
67640 KB |
1st lines differ - on the 1st token, expected: '3', found: '1' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
42 ms |
67616 KB |
1st lines differ - on the 1st token, expected: '10082010', found: '0' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
151 ms |
84672 KB |
1st lines differ - on the 1st token, expected: '40313272768926', found: '40313049006569' |
| 2 |
Halted |
0 ms |
0 KB |
- |
