#1164905 (C++14) No.855 ヘビの日光浴

• 問題: No.855 ヘビの日光浴
• ユーザー: vjudge1
• 提出日時: 2026-05-16 12:01:31
• 言語: C++14 (gcc 15.2.0 + boost 1.89.0)
• 結果: TLE
• 実行時間: -
• コード長: 3,010 bytes
• コンパイル時間: 1,374 ms
• コンパイル使用メモリ: 192,744 KB
• 実行使用メモリ: 9,600 KB
• 最終ジャッジ日時: 2026-05-16 12:02:18
• 合計ジャッジ時間: 9,588 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge3_0

ファイルパターン	結果
sample	AC * 3
other	AC * 61 TLE * 1 -- * 30

ソースコード

#include<bits/stdc++.h>
//#include<bits/extc++.h>
 
#ifdef LOCAL
#define sc cerr
#else
#define sc if(0)cerr
#pragma optimized("O2")
#endif
 
#define qlog(x) {sc<<#x<<" = "<<(x)<<"\n";}
#define rep(i,l,r) for(int i=(l);i<=(r);i++) 
#define irep(i,r,l) for(int i=(r);i>=(l);i--) 
#define qloga(a,l,r) {sc<<#a<<": "; rep(I,(l),(r)){sc<<a[I]<<" ";}sc<<"\n";}
#define qlogSTL(a) {sc<<#a<<": "; for(const auto &I:(a)){sc<<I<<" ";}sc<<"\n";}
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
//typedef __int128 i128;

struct ST{
	int n, root;
	struct node{
		int mx,ls,rs;
		node(int a,int b,int c):mx(a), ls(b), rs(c){}
	};
	vector<node> a;

	#define ls(u) (a[(u)].ls)
	#define rs(u) (a[(u)].rs)
	#define mx(u) (a[(u)].mx)
	void pushup(int u){
		mx(u)=max(mx(ls(u)),mx(rs(u)));
	}
	void modify(int p,int x,int &u,int l,int r){
		if(!u){
			a.emplace_back(0,0,0);
			u=(int)a.size()-1;
		}
		if(l==r){
			mx(u)=x;
			return;
		}
		int mid=(l+r)/2;
		if(p<=mid)modify(p,x,ls(u),l,mid);
		else modify(p,x,rs(u),mid+1,r);

		pushup(u);
	}
	ll query(int L,int R,int u,int l,int r){
		if(!u)return 0;
		if(L<=l && r<=R){ return mx(u); }

		int mid=(l+r)/2;
		ll ans=0;
		if(L<=mid)ans=max(ans,query(L,R,ls(u),l,mid));
		if(mid<R)ans=max(ans,query(L,R,rs(u),mid+1,r));
		return ans;
	}
	void modify(int p,int x){
		modify(p,x,root,1,n);
	}
	ll query(int L,int R){
		if(L>R)return 0;
		if(R>n)R=n;
		return query(L,R,root,1,n);
	}
	void add(int p,int x){
		modify(p,query(p,p)+x);
	}
	ll sum(){
		ll ans=0;
		rep(i,1,n)ans+=query(i,i);
		return ans;
	}
	ST(int _n): n(_n){
		a.emplace_back(0,0,0);
		a.reserve(5e6);
		root=0;
	}
	ST(){}
}Ls,Rs,Us,Ds;

int Q,h,w;
void _modify(ST &L, ST &R, ST &U, ST &D,int x,int v){
	int n=U.n, m=L.n;
	int cur=D.query(x,x), opp=U.query(n-x+1,n-x+1);
	D.add(x,v);
	int l=cur+1, r=m+1;
	//sc<<"["<<l<<","<<r<<"]\n";
	while(l<r){
		int mid=(l+r)/2;
		if([&](){
			return L.query(m-mid+1,m-cur+1)>=x
			    || R.query(cur,mid)>=n-x+1;
		}())r=mid;
		else l=mid+1;
	}
	sc<<r<<"/"<<m<<"\n";
	if(r<=cur+v && r<=m-opp){
		bool A=(L.query(m-r+1,m-r+1)>=x);
		bool B=(R.query(r,r)>=n-x+1);
		sc<<A<<" "<<B<<"\n";
		D.modify(x,0);
		if(A){
			L.modify(m-r+1,0);
			sc<<" ????\n";
			return;
		}else if(B){
			R.modify(r,0);
			sc<<" ????\n";
			return;
		}else{
			sc<<" !!!\n";
			exit(4);
		}
	}
	if(cur+v+opp>m){
		D.modify(x,0);
		U.modify(n-x+1,0);
		sc<<" ????\n";
	}
}
void modify(int x,int y,int v){
	if(!x)         _modify(Rs,Ls,Ds,Us,h-y+1,v);
	else if(x==w+1)_modify(Ls,Rs,Us,Ds,y,v);
	else if(!y)    _modify(Us,Ds,Rs,Ls,x,v);
	else if(y==h+1)_modify(Ds,Us,Ls,Rs,w-x+1,v);
}

signed main(){
	//freopen("snake.in","r",stdin);
	//freopen("snake.out","w",stdout);
	ios::sync_with_stdio(0); cin.tie(0);

	cin>>h>>w>>Q;
	Ls=ST(w);
	Rs=ST(w);
	Us=ST(h);
	Ds=ST(h);
	while(Q--){
		static int cnt=0;
		sc<<" ======= "<<++cnt<<" ========\n";
		int x,y,v;
		cin>>x>>y>>v;
		modify(x,y,v);
	}
	ll A=Ls.sum();
	ll B=Rs.sum();
	ll C=Us.sum();
	ll D=Ds.sum();
	cout<<A+B+C+D;
}