BARICAVN - BARICA
Tác giả: RR
Ngôn ngữ: C++
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <set>
#define MAXN 300111
#define FOR(i,a,b) for(long i=a; i<=b; i++)
#define S set< pair<long,long> >
#define FORS(s,i) for(S::iterator i=s.begin(); i!=s.end(); i++)
#define MP make_pair
using namespace std;
long n,k,targetu,targetv,startu,startv,maxX[MAXN],maxY[MAXN],f[MAXN];
pair< pair<long,long>,long> a[MAXN];
S s;
void inp() {
scanf("%ld %ld",&n,&k);
FOR(i,1,n)
scanf("%ld %ld %ld",&a[i].first.first,&a[i].first.second,&a[i].second);
}
void RR() {
//Roi rac hoa theo truc X
FOR(i,1,n)
s.insert(MP(a[i].first.first,i));
long now=s.begin()->first,ind=1;
a[s.begin()->second].first.first=1;
FORS(s,i)
if (i!=s.begin()) {
if (i->first!=now) {
ind++;
now=i->first;
}
a[i->second].first.first=ind;
}
//Roi rac hoa theo truc Y
s.clear();
FOR(i,1,n)
s.insert(MP(a[i].first.second,i));
now=s.begin()->first; ind=1;
a[s.begin()->second].first.second=1;
FORS(s,i)
if (i!=s.begin()) {
if (i->first!=now) {
ind++;
now=i->first;
}
a[i->second].first.second=ind;
}
}
void solve() {
targetu=a[n].first.first;
targetv=a[n].first.second;
startu=a[1].first.first;
startv=a[1].first.second;
sort(a+1,a+n+1);
FOR(i,1,n) {
if (a[i].first.first==startu&&a[i].first.second==startv) {
f[i]=a[i].second;
maxX[a[i].first.first]=f[i];
maxY[a[i].first.second]=f[i];
} else {
long temp=max(maxX[a[i].first.first],maxY[a[i].first.second])-k;
if (temp>=0) temp+=a[i].second; else temp=0;
f[i]=temp;
maxX[a[i].first.first]>?=f[i];
maxY[a[i].first.second]>?=f[i];
}
}
FOR(i,1,n)
if (a[i].first.first==targetu&&a[i].first.second==targetv)
printf("%ld\n",f[i]);
}
int main() {
#ifdef DEBUG
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
inp();
RR();
solve();
return 0;
}