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;
}

Download