Submission #53132

#	Time	Username	Problem	Language	Result	Execution time	Memory
53132		alenam0161	Aliens (IOI16_aliens)	C++17	4 / 100	6 ms	700 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+7;
const int M = 1e6;
int a[N];
struct po{
    long long x,y;
    po(long long fi=0,long long se=0){
        x=fi;
        y=se;
    }
    bool operator<(const po& oth)const{
        return x<oth.x;
    }
    po rev(){
    return po(y,x);
    }
};
long long get(po fi, po se){
    return llabs((llabs(se.x-fi.x)+1)*(llabs(se.y-fi.y)+1));
}
long long get_sq( po fi){
    return get(fi,fi.rev());
}
long long D(const po& fi,const po& se){
    long long d=get(po(fi.x,fi.x),po(se.y,se.y));
    d-=get_sq(fi);
    d-=get_sq(se);
    if(fi.y>=se.x){
        d+=get(po(fi.y,fi.y),po(se.x,se.x));
    }
    return d;
}
multiset<po> pw;
multiset<pair<long long,pair<po,po> > > all;
typedef  multiset<po>::iterator mpo;
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
    for(int i=0;i<n;++i){
        int x=r[i];
        int y=c[i];
        if(x>y)swap(x,y);
        a[x]=max(a[x],y-x+1);
    }
    long long cur=0;
    for(int i=0;i<=M;++i){
        cur--;
        if(a[i]>max(0ll,cur)){
            pw.insert(po(i,i+a[i]-1));
        }
        cur=max(cur,1ll*a[i]);
    }
    multiset<po>::iterator it;
    cur=-1;
    long long ans=0ll;
    for(it=pw.begin();it!=pw.end();++it){
        po c=*it;
        ans+=get(c,c.rev());
        if(cur>=c.x){
            ans-=get(po(c.x,c.x),po(cur,cur));
        }
        cur=max(cur,c.y);
    }
    po lst=po(-1,-1);
    for(it=pw.begin();it!=pw.end();++it){
        if(lst.x==-1){
            lst=*it;
            continue;
        }
        po c=*it;
        long long d=D(lst,c);
        all.insert(make_pair(d,make_pair(lst,c)));
        lst=c;
    }
    while(pw.size()>k){
        pair< long long, pair< po , po > > q=*all.begin();
        it=pw.find(q.second.first);
        mpo rg=pw.find(q.second.second);
        long long X=it->x;
        long long Y=rg->y;
        po nor=po(X,Y);
        ans+=q.first;
        all.erase(all.begin());
        mpo e=it;
        if(it!=pw.begin()){
            e--;
            all.erase(all.find(make_pair(D(*e,*it),make_pair(*e,*it))));
            all.insert(make_pair(D(*e,nor),make_pair(*e,nor)));
        }
        mpo nx=rg;
        nx++;
        if(nx!=pw.end()){
            all.erase(all.find(make_pair(D(*rg,*nx),make_pair(*rg,*nx))));
            all.insert(make_pair(D(nor,*nx),make_pair(nor,*nx)));
        }
        pw.erase(rg);
        pw.erase(it);
        pw.insert(nor);

    }
    return ans;
}

Compilation message (stderr)

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:75:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(pw.size()>k){
           ~~~~~~~~~^~

• Subtask 1: 4 / 4
• Subtask 2: 0 / 12
• Subtask 3: 0 / 9
• Subtask 4: 0 / 16
• Subtask 5: 0 / 19
• Subtask 6: 0 / 40