제출 #423892

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
423892		rumen_m	Aliens (IOI16_aliens)	C++17	100 / 100	218 ms	11644 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;
   vector <int> number;
   long long px;
   CVH()
   {
       lines.clear();
       number.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, int key)
   {
       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();number.pop_back();}
           else
            break;
       }
       lines.push_back({a,b});
       number.push_back(key);
   }
  pair < pair <long long,long long>, int>  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],number[px]};
   }

};
long long square(long long a)
{
    return a*a;
}
long long ANS[maxn],keys[maxn];
pair <long long, int> solve(long long C){
      CVH u = CVH();
    //  cout<<p[1].first<<"&&&&"<<p[1].second<<endl;
        ANS[1] = square(p[1].second-p[1].first+1)+C;
        keys[1] = 1;
         long long M = -2*(p[2].first-1);
           long long B = ANS[1] + (p[2].first-1)*(p[2].first-1)- (p.size()>2 ? max((long long) 0,p[1].second-p[1+1].first+1)* max((long long)0,p[1].second-p[1+1].first+1) : 0) ;
          //cout<<M<<" "<<B<<endl;
           u.add_line(M,B,1);
        for(long long i=2;i<p.size();i++)
        {
          // cout <<" :: "<<i<<" :::: "<<p[i].first<<" "<<p[i].second<<endl;
            auto  z = u.query(p[i].second);
            auto d = z.first;
            auto r = z.second;
           long long  ans = d.first*p[i].second+d.second+p[i].second*p[i].second+C;
            ANS[i] = ans;
            keys[i] = keys[r]+1;
            if(square(p[i].second-p[1].first+1)+C<=ANS[i]){ANS[i] = square(p[i].second-p[1].first+1)+C;keys[i]=1;}
           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,i);}

          // cout<<"&& "<<i<<" "<<ANS[i]<<" - "<<keys[i]<<endl;
        }
        return {ANS[p.size()-1],keys[p.size()-1]};
}
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]);
    }
if(p.size()==2)
{
    return square(p[1].second-p[1].first+1);
}
/*
    long long uk1 = 0, uk2 = m*m,mid;

   while(uk1<uk2)
    {
        mid = (uk1+uk2)/2;
        cout<<"SOLVE WITH"<<" "<<mid<<endl;
        auto p = solve(mid);
        cout<<"solved: "<<p.first<<" "<<p.second<<endl;
        if(p.second>k)uk1 = mid+1;
        else
            uk2 = mid;
    }
   // cout<<ANS[p.size()-1]<<endl;
    return (ANS[p.size()-1]-k*uk2);
*/
    long long uk1 = -1e12-7, uk2 = 1,mid;
  k = min(k,(long long)p.size()-1);
   while(uk1<uk2)
    {
        mid = (uk1+uk2+1)/2;
       // cout<<"SOLVE WITH"<<" "<<mid<<endl;
        auto p = solve(-mid);
      //  cout<<"solved: "<<p.first<<" "<<p.second<<endl;
        if(p.second>k)uk2 = mid-1;
        else
            uk1 = mid;
    }
    auto P = solve(-uk1);
   // cout<<ANS[p.size()-1]<<endl;
    return (ANS[p.size()-1]+k*uk1);
}

컴파일 시 표준 에러 (stderr) 메시지

aliens.cpp: In member function 'std::pair<std::pair<long long int, long long int>, int> CVH::query(long long int)':
aliens.cpp:47: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]
   47 |        while(px<lines.size()-1)
      |              ~~^~~~~~~~~~~~~~~
aliens.cpp: In function 'std::pair<long long int, int> solve(long long int)':
aliens.cpp:72: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]
   72 |         for(long long i=2;i<p.size();i++)
      |                           ~^~~~~~~~~
aliens.cpp:82: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]
   82 |            if(i<p.size()-1){
      |               ~^~~~~~~~~~~
aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:100:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |     for(i=0;i<_r.size();i++)
      |             ~^~~~~~~~~~
aliens.cpp:146:10: warning: variable 'P' set but not used [-Wunused-but-set-variable]
  146 |     auto P = solve(-uk1);
      |          ^

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