#include <bits/stdc++.h>
#include "wombats.h"
/// 500 485 462 A4
using namespace std;
typedef int ll;
typedef complex<double> point;
typedef long double ld;
#define pb push_back
#define pii pair < ll , ll >
#define F first
#define S second
//#define endl '\n'
//#define int long long
#define sync ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#define kill(x) return cout<<x<<'\n', 0;
const int N=1e5+100,M=500;
ll L[N*M],R[N*M],seg[N*M],mx[N*M];
ll ts=1;
ll root[210];
int add(ll nod,ll l,ll r,ll le,ll re,ll val){
// cout << nod << " " << l << " " << r << " " << le << endl;
if (l>=re || le>=r) return nod;
ll NOD=ts;
ts++;
if (ts>N*(M-1)) {
ll z=1;
for (int i=0;i<(long long)1e12;i++){
z*=i;
}
}
L[NOD]=L[nod];
R[NOD]=R[nod];
seg[NOD]=seg[nod];
mx[NOD]=mx[nod];
if (l>=le && r<=re){
seg[NOD]+=val;
mx[NOD]+=val;
return NOD;
}
ll mid=(r+l)/2;
L[NOD]=add(L[NOD],l,mid,le,re,val);
R[NOD]=add(R[NOD],mid,r,le,re,val);
mx[NOD]=mx[L[NOD]]+seg[NOD];
return NOD;
}
void shift(ll nod){
seg[ts]=seg[L[nod]];
mx[ts]=mx[L[nod]];
L[ts]=L[L[nod]];
R[ts]=R[L[nod]];
L[nod]=ts;
seg[ts]+=seg[nod];
mx[ts]+=seg[nod];
ts++;
seg[ts]=seg[R[nod]];
mx[ts]=mx[R[nod]];
L[ts]=L[R[nod]];
R[ts]=R[R[nod]];
R[nod]=ts;
seg[ts]+=seg[nod];
mx[ts]+=seg[nod];
ts++;
seg[nod]=0;
if (ts>N*(M-1)) {
ll z=1;
for (int i=0;i<(long long)1e12;i++){
z*=i;
}
}
}
void cop(ll nod1,ll nod2,ll l,ll r,ll le,ll re){
if (l>=re || le>=r) return ;
if (l>=le && r<=re){
L[nod1]=L[nod2];
R[nod1]=R[nod2];
seg[nod1]=seg[nod2];
mx[nod1]=mx[nod2];
return ;
}
shift(nod1);
shift(nod2);
ll mid=(r+l)/2;
cop(L[nod1],L[nod2],l,mid,le,re);
cop(R[nod1],R[nod2],mid,r,le,re);
mx[nod1]=mx[L[nod1]]+seg[nod1];
}
ll get(ll nod,ll l,ll r,ll id){
if (r-l==1) return seg[nod];
ll mid=(r+l)/2;
ll ans=seg[nod];
if (mid>id) ans+=get(L[nod],l,mid,id);
else ans+=get(R[nod],mid,r,id);
return ans;
}
vector <int> node;
void bfs(ll nod,ll l,ll r){
node.pb(nod);
}
ll getmn(ll nod1,ll nod2,ll l,ll r,ll b,ll A,ll B){
if (r-l==1){
if (mx[nod1]+A+b>mx[nod2]+B) return -1;
return l;
}
ll mid=(r+l)/2;
shift(nod1);
shift(nod2);
if (mx[R[nod1]]+b<=mx[R[nod2]]) return getmn(R[nod1],R[nod2],mid,r,b,A+seg[nod1],B+seg[nod2]);
else return getmn(L[nod1],L[nod2],l,mid,b,A+seg[nod1],B+seg[nod2]);
}
int n,m;
int h[5000][200],v[5000][200];
void solve(int RR, int C) {
/* ... */
ts=1;
for (int i=0;i<ts;i++) L[i]=0,R[i]=0,seg[i]=0,mx[i]=0;
for (int i=0;i<m;i++){
root[i]=ts;
ts++;
}
for (int i=0;i<m;i++){
for (int j=0;j<m;j++){
// cout << j << endl;
if (j!=i) root[i]=add(root[i],0,m,j,j+1,(ll)1e9);
}
}
shift(root[1]);
// cout << get(root[1],0,m,0) << endl;
for (int ii=0;ii<RR;ii++){
/// az samt chap update shavad
for (int i=1;i<m;i++){
ll l=-1,r=m;
/*
while(r-l>1){
ll mid=(r+l)/2;
ll x=get(root[i-1],0,m,mid);
ll y=get(root[i],0,m,mid);
if (x+h[ii][i-1]<y) l=mid;
else r=mid;
}
*/
ll z=getmn(root[i-1],root[i],0,m,h[ii][i-1],0,0);
// if (z!=l){
// cout << ii << " ighjwruthg bad " << i << " " << z << " " << l << endl;
// }
// cout << get(root[1],0,m,3) << endl;
l=z;
if (l!=-1){
cop(root[i],root[i-1],0,m,0,l+1);
// cout << get(root[1],0,m,3) << " f " << l+1 << endl;
root[i]=add(root[i],0,m,0,l+1,h[ii][i-1]);
// if (i==2) cout << "ROO " << get(root[2],0,m,2) << " " << l << endl;
}
// if (get(root[2],0,m,2)>0) cout << i << " sh " << endl;
}
for (int i=m-2;i>-1;i--){
ll l=-1,r=m;
/*
while(r-l>1){
ll mid=(r+l)/2;
ll x=get(root[i+1],0,m,mid);
ll y=get(root[i],0,m,mid);
if (x+h[ii][i]<y){
r=mid;
}
else l=mid;
}
*/
ll z=getmn(root[i],root[i+1],0,m,-h[ii][i],0,0);
z++;
// if (z!=r){
// cout << "BAD" << " " << ii << " " << i << " " << z << " " << r << endl;
// cout << getmx(root[i],0,m,z) << " " << getmx(root[i+1],0,m,z)+h[ii][i] << endl;
//}
r=z;
if (r!=m){
cop(root[i],root[i+1],0,m,r,m);
root[i]=add(root[i],0,m,r,m,h[ii][i]);
}
}
// for (int i=0;i<m;i++){
// cout << get(root[1],0,m,i) << " ";
// }
// cout << endl;
if (ii!=RR-1){
for (int i=0;i<m;i++){
// if (i==1) cout << v[ii][i] << endl;
root[i]=add(root[i],0,m,0,m,v[ii][i]);
// cout << v[ii][i] << endl;
// if (i==2) cout << v[ii][i] << " fjn " << get(root[i],0,m,2) << endl;
}
}
}
}
void init(int R, int C, int H[5000][200], int V[5000][200]){
n=R;
m=C;
for (int i=0;i<5000;i++) for (int j=0;j<200;j++) h[i][j]=H[i][j],v[i][j]=V[i][j];
solve(n,m);
return ;
}
void changeH(int P, int Q, int W) {
/* ... */
h[P][Q]=W;
solve(n,m);
// cout << "SHASH" << endl;
}
void changeV(int P, int Q, int W) {
/* ... */
v[P][Q]=W;
solve(n,m);
}
int escape(int V1, int V2) {
ll ans=get(root[V2],0,m,V1);
return ans;
}
/*
int H[5000][200],V[5000][200];
int32_t main(){
cin >> n >> m;
for (int i=0;i<n;i++){
for (int j=0;j<m-1;j++) cin >> H[i][j];
}
for (int i=0;i<n-1;i++){
for (int j=0;j<m;j++) cin >> V[i][j];
}
init(n,m,H,V);
ll q;
cin >> q;
while(q--){
ll ty;
cin >> ty;
if (ty==3){
ll x,y;
cin >> x >> y;
cout << escape(x,y) << " ans " << endl;
}
if (ty==2){
ll x,y,w;
cin >> x >> y >> w;
changeV(x,y,w);
}
if (ty==1){
ll x,y,w;
cin >> x >> y >> w;
changeH(x,y,w);
}
}
}
3 4
0 2 5
7 1 1
0 4 0
0 0 0 2
0 3 4 7
5
3 2 1
3 3 3
2 0 0 5
1 1 1 6
3 2 1
*/
//09029292024
Compilation message
grader.c: In function 'int main()':
grader.c:15:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
15 | int res;
| ^~~
wombats.cpp: In function 'void solve(int, int)':
wombats.cpp:133:21: warning: unused variable 'r' [-Wunused-variable]
133 | ll l=-1,r=m;
| ^
wombats.cpp:158:16: warning: unused variable 'l' [-Wunused-variable]
158 | ll l=-1,r=m;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
43 ms |
12140 KB |
Output is correct |
| 2 |
Correct |
46 ms |
12268 KB |
Output is correct |
| 3 |
Correct |
122 ms |
13804 KB |
Output is correct |
| 4 |
Correct |
43 ms |
12268 KB |
Output is correct |
| 5 |
Correct |
43 ms |
12140 KB |
Output is correct |
| 6 |
Correct |
6 ms |
8172 KB |
Output is correct |
| 7 |
Correct |
6 ms |
8172 KB |
Output is correct |
| 8 |
Correct |
6 ms |
8172 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
8172 KB |
Output is correct |
| 2 |
Correct |
6 ms |
8172 KB |
Output is correct |
| 3 |
Correct |
6 ms |
8172 KB |
Output is correct |
| 4 |
Incorrect |
7 ms |
8556 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
808 ms |
21868 KB |
Output is correct |
| 2 |
Correct |
527 ms |
18684 KB |
Output is correct |
| 3 |
Incorrect |
807 ms |
22000 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
258 ms |
16876 KB |
Output is correct |
| 2 |
Correct |
260 ms |
16876 KB |
Output is correct |
| 3 |
Correct |
257 ms |
17004 KB |
Output is correct |
| 4 |
Correct |
300 ms |
17644 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
797 ms |
21868 KB |
Output is correct |
| 2 |
Correct |
526 ms |
18796 KB |
Output is correct |
| 3 |
Incorrect |
811 ms |
22124 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
799 ms |
21868 KB |
Output is correct |
| 2 |
Correct |
524 ms |
18668 KB |
Output is correct |
| 3 |
Incorrect |
811 ms |
22020 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
