| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1125945 | ntdaccode | Catfish Farm (IOI22_fish) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
#define fori(i,a,b) for(int i=a;i<=b;i++)
#define int long long
#define pb push_back
using namespace std;
typedef pair<int,long long> ii;
typedef tuple<int,int,int> tp;
const int M = 1e6 + 10;
const int N = 3e5 + 10;
const int mod = 1e9 + 7;
int n, m ;
int xx[N], yy[N], ww[N];
int t[2][2][4 * N], lz[2][2][4 * N];
void add(int cur, int tt, int s, int val)
{
t[cur][tt][s] += val;
lz[cur][tt][s] += val;
}
void lazy(int cur, int tt, int s)
{
add(cur, tt, s * 2, lz[cur][tt][s]);
add(cur, tt, s * 2 + 1, lz[cur][tt][s]);
lz[cur][tt][s] = 0;
}
void upd(int cur, int tt, int s, int l, int r, int u, int v, int val)
{
if(u > r || v < l) return ;
if(u <= l && r <= v) {
add(cur, tt, s, val);
return ;
}
int mid = (l + r)/2;
if(l != r && lz[cur][tt][s] != 0) lazy(cur,tt,s);
upd(cur, tt, s * 2, l, mid, u, v, val);
upd(cur, tt, s * 2 + 1, mid + 1, r, u, v, val);
t[cur][tt][s] = max(t[cur][tt][s * 2], t[cur][tt][s * 2 + 1]);
}
int get(int cur,int tt,int s, int l, int r,int u,int v)
{
if(u > r || v < l) return 0;
if(u <= l && r <= v) return t[cur][tt][s];
int mid = (l + r)/2;
if(l != r && lz[cur][tt][s] != 0) lazy(cur,tt,s);
return max(get(cur, tt, s * 2, l, mid, u, v), get(cur, tt, s * 2 + 1, mid + 1, r, u, v));
}
vector<ii> Q[N];
int f[2][2][N];
// 2 tt : 1 la truoc lon hon sau 0 la con lai
int32_t main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
if(fopen("1.inp","r")) {
freopen("1.inp","r",stdin);
freopen("1.out","w",stdout);
}
#define task ""
if(fopen(task".inp","r")) {
freopen(task".inp","r",stdin);
freopen(task".out","w",stdout);
}
cin >> n >> m;
for(int i = 1;i <= n; i++) Q[i].pb({0,0});
for(int i = 1;i <= m; i++) {
cin >> xx[i] >> yy[i] >> ww[i];
xx[i]++;
yy[i]++;
Q[xx[i]].pb({yy[i],ww[i]});
}
for(int i = 1;i <= n; i++) sort(Q[i].begin(), Q[i].end());
for(int i = 1;i <= n; i++) {
int u = Q[i].back().first;
if(u != n) Q[i].pb({n,0});
}
int pre, cur;
for(int i = 2;i <= n; i++) {
//
pre = i - 1 & 1, cur = i & 1;
for(auto[pos,val] : Q[i]) {
if(val == 0) continue;
upd(pre, 0, 1, 0, n, pos, n, val);
upd(pre, 1, 1, 0, n, pos, n, val);
}
for(auto[pos,val] : Q[i]) {
if(pos != 0 && f[cur][1][pos - 1] == 0) {
int x = max(get(pre, 0, 1, 0, n, pos - 1, n), get(pre, 1, 1, 0, n, pos - 1, n));
upd(cur, 1, 1, 0, n, pos - 1, pos - 1, x);
f[cur][1][pos - 1] = x;
}
if(val != 0) {
upd(pre, 0, 1, 0, n, pos, n, -val);
upd(pre, 1, 1, 0, n, pos, n, -val);
}
int x = max(get(pre, 0, 1, 0, n, pos, n), get(pre, 1, 1, 0, n, pos, n));
upd(cur, 1, 1, 0, n, pos, pos, x);
f[cur][1][pos] = x;
//cout << i << " " << 1 << " " << pos << " " << x << "\n";
}
//
for(auto [pos,val] : Q[i - 1]) {
if(val != 0) upd(pre, 0, 1, 0, n, 0, pos - 1, val);
}
reverse(Q[i - 1].begin(), Q[i - 1].end());
// vector<int> revQ;
//
// for(int j = Q[i - 1].size() - 1;j >= 0; j--) {
// revQ.pb(Q[i - 1][j]);
// }
for(auto [pos,val] : Q[i - 1]) {
int x = max(get(pre, 0, 1, 0, n, 0, pos),get(pre, 1, 1, 0, n, 0, pos));
upd(cur, 0, 1, 0, n, pos, pos, x);
f[cur][0][pos] = x;
//cout << i << " " << 0 << " " << pos << " " << x << "\n";
if(val != 0) upd(pre, 0, 1, 0, n, 0, pos - 1, -val);
}
for(auto[pos,val] : Q[i - 1]) {
if(f[pre][1][pos]) upd(pre, 1, 1, 0, n, pos, pos, -f[pre][1][pos]);
f[pre][1][pos] = 0;
if(pos != 0 && f[pre][1][pos - 1] != 0) {
if(f[pre][1][pos - 1]) upd(pre, 1, 1, 0, n, pos - 1, pos - 1, -f[pre][1][pos - 1]);
f[pre][1][pos - 1] = 0;
}
}
if(i != 2) {
for(auto[pos,val] : Q[i - 2]) {
if(f[pre][0][pos]) upd(pre, 0, 1, 0, n, pos, pos, -f[pre][0][pos]);
f[pre][0][pos] = 0;
}
}
}
//
cout << max(t[n & 1][0][1],t[n & 1][1][1]);
// cerr << (float)clock()/CLOCKS_PER_SEC << "\n";
}