Submission #423780

#	Time	Username	Problem	Language	Result	Execution time	Memory
423780		rumen_m	Aliens (IOI16_aliens)	C++17	60 / 100	2071 ms	10360 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
const long long maxn = 100005;
long long ans[maxn][2];
long long n,m,k;
vector <pair <long long,long long> > w,p;
bool cmp(pair <long long,long long> i, pair <long long,long long> j)
{
    if(i.first==j.first)return i.second>j.second;
    return i.first<j.first;
}
struct CVH
{
   vector < pair <long long,long long> > lines;
   long long px;
   CVH()
   {
       lines.clear();
      // lines.push_back({0,0});
       px = 0;
   }
   double intersect( pair <long long, long long> l1, pair <long long,long long> l2)
   {
       return (double)(l2.second-l1.second)/(l1.first-l2.first);
   }
   void add_line(long long a, long long b)
   {
       while(lines.size()>=2)
       {
           auto l1 = lines.back();
           auto l2 = lines[lines.size()-2];
           //if((l2.second-l1.first)*(l2.first-)
           if(intersect(l1,l2)>intersect(l2,{a,b}))lines.pop_back();
           else
            break;
       }
       lines.push_back({a,b});
   }
   pair <long long,long long> query(long long x)
   {
       //cout<<"HERE"<<endl;
       //if(lines.size()==1)return {0,0};
       while(px<lines.size()-1)
       {
           if(lines[px].first*x+lines[px].second>=lines[px+1].first*x+lines[px+1].second)px++;
           else
            break;
       }
       //cout<<"FOUND"<<px<<endl;
       return lines[px];
   }

};
long long square(long long a)
{
    return a*a;
}
long long ANS[maxn];
long long take_photos(int _n, int _m, int _k, std::vector<int> _r, std::vector<int> _c) {
    n = _n;
    m = _m;
    k = _k;
    w.resize(n);
    long long i;
    for(i=0;i<_r.size();i++)
    {
        _r[i]++;
        _c[i]++;
        w[i].first = min(_r[i],_c[i]);
        w[i].second = max(_r[i],_c[i]);
    }
    sort(w.begin(),w.end(),cmp);
    p.push_back({0,0});
    for(i=0;i<n;i++)
    {
        if(p.back().first<=w[i].first&&w[i].second<=p.back().second)continue;
        p.push_back(w[i]);
    }
    CVH u,v;
    for(int i = 1; i<p.size();i++)
    {
        ANS[i] = square(p[i].second-p[1].first+1);
        //cout<<i<<"->"<<ANS[i]<<" "<<p[i].first<<" "<<p[i].second<<endl;
    }

    for(long long j = 2; j<=k; j++)
    {
        u = CVH();
         long long M = -2*(p[2].first-1);
           long long B = ANS[1] + (p[2].first-1)*(p[2].first-1)- max((long long) 0,p[1].second-p[1+1].first+1)* max((long long)0,p[1].second-p[1+1].first+1) ;
           //cout<<M<<" "<<B<<endl;
           u.add_line(M,B);
        for(long long i=2;i<p.size();i++)
        {
           // cout <<j <<" :: "<<i<<" :::: "<<p[i].first<<" "<<p[i].second<<endl;
            auto  d = u.query(p[i].second);
           long long  ans = d.first*p[i].second+d.second+p[i].second*p[i].second;
           if(i<p.size()-1){
           long long M = -2*(p[i+1].first-1);
           long long B = ANS[i] + (p[i+1].first-1)*(p[i+1].first-1) -  max((long long) 0,p[i].second-p[i+1].first+1)* max((long long)0,p[i].second-p[i+1].first+1);
          // cout<<M<<" "<<B<<endl;
           u.add_line(M,B);}
           ANS[i] = ans;
           //cout<<"&& "<<i<<" "<<ANS[i]<<endl;
        }
    }
   // cout<<ANS[p.size()-1]<<endl;
    return ANS[p.size()-1];
}

Compilation message (stderr)

aliens.cpp: In member function 'std::pair<long long int, long long int> CVH::query(long long int)':
aliens.cpp:44:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |        while(px<lines.size()-1)
      |              ~~^~~~~~~~~~~~~~~
aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:66:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |     for(i=0;i<_r.size();i++)
      |             ~^~~~~~~~~~
aliens.cpp:81:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |     for(int i = 1; i<p.size();i++)
      |                    ~^~~~~~~~~
aliens.cpp:94:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |         for(long long i=2;i<p.size();i++)
      |                           ~^~~~~~~~~
aliens.cpp:99:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |            if(i<p.size()-1){
      |               ~^~~~~~~~~~~

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