#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
set<int>fishies[100010];
map<int,ll>fishiess[100010];
unordered_map<int,ll>dp[100010][2];
int N;
inline ll ones(int col,int len){
return (--fishiess[col].upper_bound(len))->second;
}
struct segtree{
ll T[1<<18];
ll query(int i,int l,int r,int ll,int rr){
if(l>rr||ll>r) return -1e18;
if(ll<=l&&r<=rr) return T[i];
return max(query(i*2,l,l+r>>1,ll,rr),
query(i*2+1,l+r+2>>1,r,ll,rr));
}
void upd(int i,int l,int r,int p,ll x){
if(l==r)return void(T[i]=x);
if(l+r>>1>=p)upd(i*2,l,l+r>>1,p,x);
else upd(i*2+1,l+r+2>>1,r,p,x);
T[i]=max(T[i*2],T[i*2+1]);
}
};
struct a_data_type{
segtree Sec,First,Overal,Third;
inline ll sec(int pos){
return Sec.query(1,0,N,pos,N);
}
inline ll first(int pos){
return First.query(1,0,N,0,pos);
}
inline ll overal(int pos){
return Overal.query(1,0,N,pos,N);
}
inline ll third(int pos){
return Third.query(1,0,N,0,pos);
}
set<int>prv;
void init(int i) {
for(auto j:prv)
Overal.upd(1,0,N,j,0),
First.upd(1,0,N,j,0),
Sec.upd(1,0,N,j,0),
Third.upd(1,0,N,j,0);
prv.clear();
for(auto j:fishies[i]){
prv.insert(--j);
ll A=dp[i][0][j];
ll B=dp[i][1][j];
Overal.upd(1,0,N,j,max(A,B));
First.upd(1,0,N,j,max(A,B)-ones(i+1,j));
Sec.upd(1,0,N,j,A);
Third.upd(1,0,N,j,B-ones(i,j)-ones(i+1,j));
}
}
} likehell[2];
ll max_weights(int N_,int M,vector<int> X,vector<int> Y,vector<int> W) {
N=N_;
for(int i=0;i<M;i++)
fishies[X[i]+1].insert(Y[i]+1),
fishiess[X[i]+1][Y[i]+1]=W[i];
for(int i=1;i<=N;i++){
fishiess[i][N+1];
fishiess[i][0];
auto it=++fishiess[i].begin();
while(it!=fishiess[i].end())
it->second+=prev(it)->second,it++;
}
for(int i=1;i<=N;i++)
fishies[i].insert(1),
fishies[i].insert(N+1);
fishies[N+1].insert(0);
for(auto i:fishies[1])
dp[1][1][i-1]=ones(2,i-1);
int b=0;
likehell[b].init(1);
for(int i=2;i<=N;i++){
for(auto rw:fishies[i]) {
ll cons=ones(i+1,rw-1)+ones(i-1,rw-1);
ll F=likehell[!b].first(rw-1);
ll S=likehell[!b].overal(rw)-ones(i-1,rw-1);
dp[i][1][rw-1]=cons+max(F,S);
}
for(auto rw2:fishies[i]){
ll cons=ones(i+1,rw2-1)+ones(i-1,rw2-1);
ll F=likehell[b].third(rw2-1);
ll S=likehell[b].overal(rw2);
dp[i][1][rw2-1]=max(dp[i][1][rw2-1],F+cons);
dp[i][0][rw2-1]=S-ones(i,rw2-1)-ones(i-1,rw2-1)+cons;
}
for(auto rw2:fishies[i]) {
ll K=likehell[b].sec(rw2-1)-ones(i,rw2-1);
dp[i][0][rw2-1]=max(dp[i][0][rw2-1],ones(i+1,rw2-1)+K);
}
b=!b;
likehell[b].init(i);
}
return likehell[b].overal(0);
}
Compilation message
fish.cpp: In member function 'll segtree::query(int, int, int, int, int)':
fish.cpp:17:33: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
17 | return max(query(i*2,l,l+r>>1,ll,rr),
| ~^~
fish.cpp:18:32: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
18 | query(i*2+1,l+r+2>>1,r,ll,rr));
| ~~~^~
fish.cpp: In member function 'void segtree::upd(int, int, int, int, ll)':
fish.cpp:22:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
22 | if(l+r>>1>=p)upd(i*2,l,l+r>>1,p,x);
| ~^~
fish.cpp:22:33: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
22 | if(l+r>>1>=p)upd(i*2,l,l+r>>1,p,x);
| ~^~
fish.cpp:23:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
23 | else upd(i*2+1,l+r+2>>1,r,p,x);
| ~~~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
296 ms |
202848 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
21 ms |
66392 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
219 ms |
176724 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
22 ms |
66320 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
22 ms |
66320 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
22 ms |
66320 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
219 ms |
176724 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
296 ms |
202848 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
