Submission #78547

#	Time	Username	Problem	Language	Result	Execution time	Memory
78547		nxteru	Bulldozer (JOI17_bulldozer)	C++14	5 / 100	15 ms	764 KiB

bulldozer

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <cstdio>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
#define F first
#define S second
#define PB push_back
#define INF 100000000000000000
struct li{
  ll a,b;
  bool operator<(const li&q)const{
      return b*q.a<q.b*a;
  }
};
struct qu{
  ll x,y,a,b;
  bool operator<(const qu&q)const{
      if(x==0||q.x==0)return x*y>q.x*q.y;
      if(x*y>0==q.x*q.y>0)return y*q.x<x*q.y;
      return x*y>q.x*q.y;
  }
  bool operator>(const qu&q)const{
      if(x==0||q.x==0)return x*y<q.x*q.y;
      if(x*y>0==q.x*q.y>0)return y*q.x>x*q.y;
      return x*y<q.x*q.y;
  }
};
struct poi{
  ll x,y,i;
  bool operator<(const poi&q)const{
      if(y!=q.y)return y<q.y;
      return x>q.x;
  }
  bool operator>(const poi&q)const{
      if(y!=q.y)return y>q.y;
      return x<q.x;
  }
};
ll n,x[2005],y[2005],w[2005],k,pl[2005],ans,la[1<<12];
P seg[1<<12];
vector<P>lin[2005];
map<li,int>o;
vector<qu>q;
vector<poi>po;
void lazy(int l,int r,int v){
    if(la[v]==0)return;
    seg[v].F+=la[v];
    seg[v].S+=la[v];
    if(l!=r){
        la[v*2+1]+=la[v];
        la[v*2+2]+=la[v];
    }
    la[v]=0;
}
void add(int a,int b,int l,int r,int v,ll c){
    if(r<a||b<l){
        lazy(l,r,v);
        return;
    }
    if(a<=l&&r<=b){
        la[v]+=c;
        lazy(l,r,v);
        return;
    }
    lazy(l,r,v);
    add(a,b,l,(l+r-1)/2,v*2+1,c);
    add(a,b,(l+r+1)/2,r,v*2+2,c);
    seg[v].F=max(seg[v*2+1].F,seg[v*2+2].F);
    seg[v].S=min(seg[v*2+1].S,seg[v*2+2].S);
}
ll ma(int a,int b,int l,int r,int v){
    lazy(l,r,v);
    if(r<a||b<l)return 0;
    if(a<=l&&r<=b)return seg[v].F;
    return max(ma(a,b,l,(l+r-1)/2,v*2+1),ma(a,b,(l+r+1)/2,r,v*2+2));
}
ll mi(int a,int b,int l,int r,int v){
    lazy(l,r,v);
    if(r<a||b<l)return INF;
    if(a<=l&&r<=b)return seg[v].S;
    return min(mi(a,b,l,(l+r-1)/2,v*2+1),mi(a,b,(l+r+1)/2,r,v*2+2));
}
int main(void){
    scanf("%lld",&n);
    for(int i=0;i<n;i++){
        scanf("%lld%lld%lld",x+i,y+i,w+i);
        po.PB(poi{x[i],y[i],i});
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<k;j++)lin[j].clear();
        k=0;
        o.clear();
        for(int j=i+1;j<n;j++){
            if(y[i]==y[j])continue;
            li z={x[i]-x[j],y[i]-y[j]};
            if(o.find(z)==o.end()){
                lin[k].PB(P(y[i],i));
                o[z]=k++;
            }
            lin[o[z]].PB(P(y[j],j));
        }
        for(int j=0;j<k;j++){
            sort(lin[j].begin(),lin[j].end());
            for(int r=0;r<lin[j].size()-1-r;r++){
                int v=lin[j][r].S,u=lin[j][lin[j].size()-1-r].S;
                q.PB(qu{x[v]-x[u],y[v]-y[u],v,u});
            }
        }
    }
    sort(po.begin(),po.end());
    ll m=0,s=0;
    for(int i=0;i<n;i++){
        pl[po[i].i]=i+1;
        s+=w[po[i].i];
        add(i+1,i+1,0,(1<<11)-1,0,s);
        ans=max(ans,s-m);
        m=min(m,s);
    }
    sort(q.begin(),q.end());
    for(int i=0;i<q.size();i++){
        vector<P>t;
        t.PB(P(q[i].a,q[i].b));
        while(i+1<q.size()&&q[i].y*q[i+1].x==q[i+1].y==q[i].x){
            i++;
            t.PB(P(q[i].a,q[i].b));
        }
        for(int j=0;j<t.size();j++){
            int a=pl[t[j].F],b=pl[t[j].S],wa=w[t[j].F],wb=w[t[j].S];
            if(a>b){
                swap(a,b);
                swap(wa,wb);
            }
            add(a,b-1,0,(1<<11)-1,0,-wa+wb);
            pl[t[j].F]=b;
            pl[t[j].S]=a;
        }
        for(int j=0;j<t.size();j++){
            int a=pl[t[j].F],b=pl[t[j].S];
            ans=max(ans,mi(a,a,0,(1<<11)-1,0)-mi(0,a,0,(1<<11)-1,0));
            ans=max(ans,ma(a,n,0,(1<<11)-1,0)-mi(a-1,a-1,0,(1<<11)-1,0));
            ans=max(ans,mi(b,b,0,(1<<11)-1,0)-mi(0,b,0,(1<<11)-1,0));
            ans=max(ans,ma(b,n,0,(1<<11)-1,0)-mi(b-1,b-1,0,(1<<11)-1,0));
        }
    }
    printf("%lld\n",ans);
}

Compilation message (stderr)

bulldozer.cpp: In member function 'bool qu::operator<(const qu&) const':
bulldozer.cpp:23:13: warning: suggest parentheses around comparison in operand of '==' [-Wparentheses]
       if(x*y>0==q.x*q.y>0)return y*q.x<x*q.y;
          ~~~^~
bulldozer.cpp: In member function 'bool qu::operator>(const qu&) const':
bulldozer.cpp:28:13: warning: suggest parentheses around comparison in operand of '==' [-Wparentheses]
       if(x*y>0==q.x*q.y>0)return y*q.x>x*q.y;
          ~~~^~
bulldozer.cpp: In function 'int main()':
bulldozer.cpp:108:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int r=0;r<lin[j].size()-1-r;r++){
                         ~^~~~~~~~~~~~~~~~~~
bulldozer.cpp:124:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<q.size();i++){
                 ~^~~~~~~~~
bulldozer.cpp:127:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(i+1<q.size()&&q[i].y*q[i+1].x==q[i+1].y==q[i].x){
               ~~~^~~~~~~~~
bulldozer.cpp:127:44: warning: suggest parentheses around comparison in operand of '==' [-Wparentheses]
         while(i+1<q.size()&&q[i].y*q[i+1].x==q[i+1].y==q[i].x){
bulldozer.cpp:131:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0;j<t.size();j++){
                     ~^~~~~~~~~
bulldozer.cpp:141:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0;j<t.size();j++){
                     ~^~~~~~~~~
bulldozer.cpp:88:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld",&n);
     ~~~~~^~~~~~~~~~~
bulldozer.cpp:90:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld%lld%lld",x+i,y+i,w+i);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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