Submission #22600

#	Time	Username	Problem	Language	Result	Execution time	Memory
22600		버거킹 송죽SK점 우수고객 (#40)	Donut-shaped Enclosure (KRIII5_DE)	C++11	7 / 7	763 ms	49440 KiB

DE

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pp;
typedef pair<ll,ll> pll;
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define x first
#define y second
const ll inf = (1LL << 60);
#define yn namseo

int n;
ll l, r;

typedef tuple<ll,ll,ll,ll,ll> rect;
vector<rect> rs;

void in(){
	scanf("%d%lld%lld", &n, &l, &r);
	for(int i=1; i<=n; ++i){
		ll x, y, s;
		scanf("%lld%lld%lld", &x, &y, &s);
		rs.emplace_back(x-2*r, x, y-2*r, y, s);
		rs.emplace_back(x-r-l+1, x-(r-l)-1, y-r-l+1, y-(r-l)-1, -s);
	}
}

vector<ll> YS;
int yn;

void compress(){
	YS.pb(inf);
	for(auto& tmp:rs){
		int d=get<2>(tmp), u=get<3>(tmp);
		YS.pb(d);
		YS.pb(u+1);
	}
	sort(all(YS));
	YS.erase(unique(all(YS)), YS.end());
	yn=YS.size()-1;
}

typedef tuple<ll,ll,ll,ll> Q;
vector<Q> qs;
void make_query(){
	qs.reserve(4*n);
	for(auto& tmp:rs){
		ll l,r,d,u,s; tie(l,r,d,u,s)=tmp;
		d=lower_bound(all(YS), d) - YS.begin();
		u=lower_bound(all(YS), u+1) - YS.begin() - 1;
		qs.emplace_back(l, d, u, s);
		qs.emplace_back(r+1, d, u, -s);
	}
	sort(all(qs));
}

struct SEG {
	int N;
	ll tmax[1048576];
	ll lazy[1048576];
	
	void init(int n){
		N=n;
	}
	
	inline void pd(int p, int l, int r){
		if(l==r) return;
		ll d=lazy[p];
		tmax[p*2] += d;
		lazy[p*2] += d;
		tmax[p*2+1] += d;
		lazy[p*2+1] += d;
		lazy[p]=0;
	}
	
	void update(int l, int r, int s, int p, int ml, int mr){
		pd(p, ml, mr);
		if(l<=ml && mr<=r){
			tmax[p]+=s;
			lazy[p]+=s;
			return;
		}
		if(r<ml || mr<l) return;
		int mid=(ml+mr)/2;
		update(l,r,s, p*2, ml, mid);
		update(l,r,s, p*2+1, mid+1, mr);
		tmax[p]=max(tmax[p*2], tmax[p*2+1]);
	}
	
	ll get_max(){
		return tmax[1];
	}

} seg;

int main()
{
	//freopen("in", "r", stdin);
	in();
	compress();
	make_query();
	
	seg.init(yn);
	ll ans = 0;
	ll last_x = -inf;
	for(auto& q:qs){
		ll x, d, u, s;
		tie(x, d, u, s) = q;
		if(last_x != x) ans=max(ans, seg.get_max());
		last_x = x;
		seg.update(d, u, s, 1, 0, yn-1);
	}
	printf("%lld\n", ans);
    return 0;
}

Compilation message (stderr)

DE.cpp: In function 'void in()':
DE.cpp:20:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%lld%lld", &n, &l, &r);
                                 ^
DE.cpp:23:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld%lld", &x, &y, &s);
                                    ^

• Subtask 1: 2 / 2
• Subtask 2: 5 / 5