Submission #238500

#	Time	Username	Problem	Language	Result	Execution time	Memory
238500		m3r8	Bulldozer (JOI17_bulldozer)	C++14	100 / 100	1509 ms	37540 KiB

bulldozer

#include <stdio.h>
#include <vector>
#include <algorithm>
#include <utility>
#include <functional>

#define ii std::pair<int,int>
#define iil std::pair<long long,long long>
#define ll long long
#define N 2200
#define left(i) (i << 1)
#define right(i) ((i << 1)+1)

typedef struct trr{
  ll pre;
  ll suf;
  ll best;
  ll sum;
}trr;

trr seg[N * 4];

void update(int idx, int l, int r, int v, ll x){
  if(l >= r)return;  
  if(l == r-1){
    if(x > 0){
      seg[idx].pre = x;  
      seg[idx].suf = x;
      seg[idx].best = x;    
    }else{
      seg[idx].pre = 0;  
      seg[idx].suf = 0;
      seg[idx].best = 0;    
    };
    seg[idx].sum = x;
  }else{
    int m = (l + r)>>1;
    if(v < m){
      update(left(idx),l,m,v,x);
    }else{
      update(right(idx),m,r,v,x);
    };  
    seg[idx].pre = std::max(seg[left(idx)].pre,seg[right(idx)].pre + seg[left(idx)].sum);
    seg[idx].suf = std::max(seg[right(idx)].suf,seg[left(idx)].suf + seg[right(idx)].sum);
    seg[idx].sum = seg[left(idx)].sum + seg[right(idx)].sum;
    seg[idx].best = std::max(seg[left(idx)].best,seg[right(idx)].best);
    seg[idx].best = std::max(seg[idx].best,seg[left(idx)].suf + seg[right(idx)].pre);
  };
};


long long ccw(iil a, iil b){
  return a.first * b.second - b.first * a.second;  
};

iil pp[N];
std::vector<ii> evt;
int pos[N];
int used[N];
ll value[N];
std::vector<int> col[N];
std::vector<ii> aktEvt;
int n;

int preCmp(int a, int b){
  return pos[a] < pos[b];  
};

int ptsCmp(int a, int b){
  if(pp[a].second != pp[b].second)return pp[a].second < pp[b].second;
  else return pp[a].first < pp[b].first;
};

ll evtCmp(ii a, ii b){
  ll x1 = pp[a.first].first-pp[a.second].first;  
  ll y1 = pp[a.first].second-pp[a.second].second;
  if(y1 < 0){
    x1 *= -1;  
    y1 *= -1;
  };
  if(y1 == 0){
    x1 = std::abs(x1);  
  };

  ll x2 = pp[b.first].first - pp[b.second].first;
  ll y2 = pp[b.first].second - pp[b.second].second;
  if(y2 < 0){
    x2 *= -1;  
    y2 *= -1;
  };
  if(y2 == 0){
    x2 = std::abs(x2);  
  };

  return ccw({x1,y1},{x2,y2});
};

int evtCcmp(ii a, ii b){
  return evtCmp(a, b) > 0; 
}; 

void swp(int idx1, int idx2){
  update(1,0,n,pos[idx1],value[idx2]);  
  update(1,0,n,pos[idx2],value[idx1]);  
  int tmp = pos[idx1];
  pos[idx1] = pos[idx2];
  pos[idx2] = tmp;
};


void handleCo(int idx){
  col[idx].push_back(idx);
  std::sort(col[idx].begin(),col[idx].end(),preCmp);  
  int len = col[idx].size();
  for(int i = 0;i<len>>1;i++){
    swp(col[idx][i], col[idx][len-i-1]);
  };
  for(auto i: col[idx]){
    used[i] = 1;  
  };
};

ll handleEvt(){
  for(auto i: aktEvt){
    col[i.first].push_back(i.second);
    col[i.second].push_back(i.first);
  };  
  for(auto i: aktEvt){
    if(!used[i.first]){
      handleCo(i.first);
    };  
  };
  for(auto i: aktEvt){
    used[i.first] = 0;  
    used[i.second] = 0;
    col[i.first].clear();
    col[i.second].clear();
  };
  return seg[1].best;
};

std::vector<int> pts;

int main(void){
  scanf("%d",&n);  
  for(int i = 0;i<n;i++){
    scanf("%lld %lld %lld\n",&(pp[i].first),&(pp[i].second),&value[i]);  
  };
  for(int i = 0;i<n;i++){
    for(int j = 0;j<i;j++){
      evt.push_back({i,j});
    };  
  };
  std::sort(evt.begin(),evt.end(),evtCcmp);
  for(int i = 0;i<n;i++){
    pts.push_back(i);
  };
  std::sort(pts.begin(),pts.end(),ptsCmp);
  for(int i = 0;i<n;i++){
    pos[pts[i]] = i;  
  };
  /*
  for(int i = 0;i<n;i++){
    printf("%d %d\n",i,pos[i]);  
  };
  puts("");
  */
  for(int i = 0;i<n;i++){
    update(1,0,n,i,value[pts[i]]);  
  };
  ll mx = 0;
  mx = std::max(mx,seg[1].best);
 // printf("%d\n",mx);
  int idx = 0;
  while(idx < evt.size()){
    aktEvt.push_back(evt[idx]);
    while(idx < evt.size()-1 && evtCmp(evt[idx],evt[idx+1]) == 0){
      aktEvt.push_back(evt[++idx]);
    };  
    mx = std::max(mx,handleEvt());
    /*
    printf("%d\n",mx);
    printf("%d %d %d\n\n",aktEvt[0].first,aktEvt[0].second,aktEvt.size());
    for(int i = 0;i<n;i++){
      printf("%d %d\n",i,pos[i]);  
    };
    puts("");
    */
    aktEvt.clear();
    idx++;
  };
  printf("%lld\n", mx);
  return 0;
};

Compilation message (stderr)

bulldozer.cpp: In function 'int main()':
bulldozer.cpp:175:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(idx < evt.size()){
         ~~~~^~~~~~~~~~~~
bulldozer.cpp:177:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(idx < evt.size()-1 && evtCmp(evt[idx],evt[idx+1]) == 0){
           ~~~~^~~~~~~~~~~~~~
bulldozer.cpp:145:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&n);  
   ~~~~~^~~~~~~~~
bulldozer.cpp:147:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld %lld %lld\n",&(pp[i].first),&(pp[i].second),&value[i]);  
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 20 / 20
• Subtask 3: 35 / 35
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20