Submission #189139

#	Time	Username	Problem	Language	Result	Execution time	Memory
189139		stefanbalaz2	Bulldozer (JOI17_bulldozer)	C++14	5 / 100	25 ms	1016 KiB

bulldozer

/*



*/
#include<bits/stdc++.h>
#define ff first
#define ss second
#define lld long long
#define pb push_back
using namespace std;
typedef pair<lld,lld> pii;
const int maxn=2e3+10;
lld inf=2e9;
lld rez=-inf*inf,pref[maxn],tree[maxn*4];
int n,curr_here[maxn],curr_pos[maxn];
struct srt_pii{
    bool operator ()(pii a,pii b){
        ///if(a.ff==-inf || b.ff==-inf)return a.ff<b.ff;
        if(a.ff==0 || b.ff==0){
            if(a.ff==0 && b.ff==0)return false;

            if(b.ff==0 && a.ff>0)return false;
            if(b.ff==0 && a.ff<0)return true;

            if(a.ff==0 && b.ff<0)return false;
            if(a.ff==0 && b.ff>0)return true;
        }
        return a.ff*b.ss<b.ff*a.ss;
    }
};
map<pii,vector<int>,srt_pii>mapa;
struct st{
    lld x,y,w;
    int id;
}p[maxn];
bool srt(st a,st b){
    return (a.y<b.y)||(a.y==b.y && a.x<b.x);
}
void regulate(pii &x){

    lld g=__gcd(x.ff,x.ss);
    x.ff/=g;
    x.ss/=g;

    int cnt=0;
    if(x.ff<0)cnt++;
    if(x.ss<0)cnt++;

    if(cnt==2){
        x.ff*=-1;
        x.ss*=-1;
    }
    else if(cnt==1){
        if(x.ss<0){
            x.ss*=-1;
            x.ff*=-1;
        }
    }
}
pii get_line(st a,st b){

    pii ret={0,0};

    if(a.x==b.x)return {-inf,-inf};
    if(a.y==b.y)return {0,0};
    ret={a.y-b.y,a.x-b.x};
    regulate(ret);

    return ret;
}
void degree90(pii &x){

    if(x.ff==-inf){
        x={0,0};
        return;
    }
    if(x.ff==0){
        x={-inf,-inf};
        return;
    }

    swap(x.ff,x.ss);
    x.ff*=-1;
    regulate(x);
}
void add_pair(st a,st b){

    pii pom=get_line(a,b);

    ///printf("%lld %lld   TACK1\n",a.x,a.y);

    degree90(pom);

    ///printf("%lld %lld   TACK2\n",b.x,b.y);
    ///printf("%lld %lld   LINEJA2\n",pom.ff,pom.ss);

    mapa[pom].pb(a.id);
    mapa[pom].pb(b.id);
}
void extract_pairs(){

    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
            add_pair(p[i],p[j]);
}
void update(int x,int l,int r,int id,lld val){
    if(l==r){
        tree[x]=val;
        return;
    }
    int mid=(l+r)/2;
    if(id>mid)update(x*2+1,mid+1,r,id,val);
    else update(x*2,l,mid,id,val);
    tree[x]=min(tree[x*2],tree[x*2+1]);
}
lld query(int x,int l,int r,int ll,int rr){
    if(l>rr || r<ll)return inf;
    if(l>=ll && r<=rr)return tree[x];
    int mid=(l+r)/2;
    return min(query(x*2,l,mid,ll,rr),query(x*2+1,mid+1,r,ll,rr));
}
void make_seg_tree(){

    lld minn=0;
    update(1,0,n,0,0);
    for(int i=1;i<=n;i++){
        pref[i]=pref[i-1]+p[i].w;
        update(1,0,n,i,pref[i]);
        minn=min(minn,pref[i]);

        rez=max(rez,pref[i]-minn);
    }
}
void process(vector<int> &vect){

    sort(vect.begin(),vect.end());

    int rr=vect.size()-1;
    int i;
    for(i=0;i<rr;i++,rr--){

       /// printf("%d %d AAFEWJKNGE\n",i,rr);

        int id1=vect[i];
        int id2=vect[rr];

        swap(curr_here[id1],curr_here[id2]);
        swap(curr_pos[curr_here[id1]],curr_pos[curr_here[id2]]);
        swap(p[id1],p[id2]);

        ///printf("%lld %lld %d  jeboteee\n",p[id1].x,p[id1].y,id1);
        pref[id1]=pref[id1-1]+p[id1].w;
        update(1,0,n,id1,pref[id1]);
    }

    for(;i<vect.size();i++){
        int id=vect[i];

        pref[id]=pref[id-1]+p[id].w;
        update(1,0,n,id,pref[id]);
    }
}
int main(){

    ///freopen("test.txt","r",stdin);

    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%lld %lld %lld",&p[i].x,&p[i].y,&p[i].w),p[i].id=i;

    sort(p+1,p+n+1,srt);
    for(int i=1;i<=n;i++){
         ///printf("%lld %lld  pts\n",p[i].x,p[i].y);

        curr_here[i]=p[i].id;
        curr_pos[p[i].id]=i;
    }
    extract_pairs();
    make_seg_tree();

    /*printf("%lld %d AAA\n",rez,mapa.size());
    for(int i=1;i<=n;i++)printf("%lld %lld  |  ",p[i].x,p[i].y);
    printf("\n");
    for(int i=1;i<=n;i++)printf("%lld ",pref[i]);
    printf("\n");*/

    for(map<pii,vector<int> >::iterator it=mapa.begin();it!=mapa.end();it++){
        vector<int> vect=it->ss;
        sort(vect.begin(),vect.end());
        vect.resize(unique(vect.begin(),vect.end())-vect.begin());
        int pos[vect.size()+10];
        memset(pos,0,sizeof(pos));

        ///printf("%lld %lld  KKK\n",it->ff.ff,it->ff.ss);

        /*for(int i=0;i<vect.size();i++)
            printf("%lld %lld point\n",p[curr_pos[vect[i]]].x,p[curr_pos[vect[i]]].y);*/

        for(int i=0;i<vect.size();i++){


            if(pos[i])continue;
            int id1=vect[i];
            id1=curr_pos[id1];
            pos[i]=1;

            vector<int>curr;
            curr.pb(id1);

            for(int j=i+1;j<vect.size();j++){
                if(pos[j])continue;
                int id2=vect[j];
                id2=curr_pos[id2];

                pii pom=get_line(p[id1],p[id2]);
                degree90(pom);

                if(pom==it->ff){
                    curr.pb(id2);
                    pos[j]=1;
                }
            }

            process(curr);
        }


        /*for(int i=1;i<=n;i++)printf("%lld %lld  |  ",p[i].x,p[i].y);
        printf("\n");
        for(int i=1;i<=n;i++)printf("%lld ",pref[i]);
        printf("\n");*/

        for(int i=0;i<vect.size();i++){
            int id=curr_pos[vect[i]];

            ///printf("%d %lld %lld %lld ALAA JBTR\n",id,pref[id],query(1,0,n,0,id-1),query(1,0,n,0,0));
            rez=max(rez,pref[id]-query(1,0,n,0,id-1));
        }
    }

    printf("%lld\n",rez);

return 0;
}

Compilation message (stderr)

bulldozer.cpp: In function 'void process(std::vector<int>&)':
bulldozer.cpp:157:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(;i<vect.size();i++){
          ~^~~~~~~~~~~~
bulldozer.cpp: In function 'int main()':
bulldozer.cpp:199:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<vect.size();i++){
                     ~^~~~~~~~~~~~
bulldozer.cpp:210:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j=i+1;j<vect.size();j++){
                           ~^~~~~~~~~~~~
bulldozer.cpp:233:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<vect.size();i++){
                     ~^~~~~~~~~~~~
bulldozer.cpp:168:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
bulldozer.cpp:169:73: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i=1;i<=n;i++)scanf("%lld %lld %lld",&p[i].x,&p[i].y,&p[i].w),p[i].id=i;
                          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~

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