Submission #1131100

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131100		huutuan	IOI Fever (JOI21_fever)	C++20	25 / 100	5095 ms	149544 KiB

fever

#include <bits/stdc++.h>

using namespace std;

#define int long long

struct Point{
   int x, y;
   Point (int _x=0, int _y=0){
      x=_x, y=_y;
   }
   Point operator+(Point &a){ return Point(x+a.x, y+a.y); }
   Point operator-(Point &a){ return Point(x-a.x, y-a.y); }
   Point operator*(int d){ return Point(x*d, y*d); }
};

const int N=1e5+10;
int n;
Point a[N], b[N];
int f[N];
int p1[N], p2[N], p3[N], p4[N];
pair<int, int> i1[N], i2[N], i3[N], i4[N];
int id1[N], id2[N], id3[N], id4[N];

int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   cin >> n;
   for (int i=1; i<=n; ++i) cin >> a[i].x >> a[i].y;
   // for (int i=1; i<=n; ++i) cout << -(a[i]-a[1]).y << ' ' << (a[i]-a[1]).x << '\n';
   for (int i=n; i>=1; --i) a[i]=(a[i]-a[1])*2;
   int ans=0;
   auto dist=[&](int i, int j){
      return (abs(a[i].x-a[j].x)+abs(a[i].y-a[j].y))/2;
   };
   auto calc=[&](){
      for (int i=1; i<=n; ++i){
         if (a[i].y>=a[i].x && a[i].y<=-a[i].x) b[i]=Point(1, 0);
         else if (a[i].y<=-a[i].x) b[i]=Point(0, 1);
         else if (a[i].y>=a[i].x) b[i]=Point(0, -1);
         else b[i]=Point(-1, 0);
         p1[i]=p2[i]=p3[i]=p4[i]=-1;
      }
      for (int i=1; i<=n; ++i) i1[i]={a[i].x, b[i].y==-1}, i2[i]={a[i].y, b[i].x==-1}, i3[i]={a[i].x-a[i].y, (b[i].y==-1 || b[i].x==-1)}, i4[i]={a[i].x+a[i].y, (b[i].y==1 || b[i].x==-1)};
      map<pair<int, int>, vector<int>> _m1, _m2, _m3, _m4;
      for (int i=1; i<=n; ++i){
         _m1[i1[i]].push_back(i);
         _m2[i2[i]].push_back(i);
         _m3[i3[i]].push_back(i);
         _m4[i4[i]].push_back(i);
         _m1.insert({{i1[i].first, i1[i].second^1}, {}});
         _m2.insert({{i2[i].first, i2[i].second^1}, {}});
         _m3.insert({{i3[i].first, i3[i].second^1}, {}});
         _m4.insert({{i4[i].first, i4[i].second^1}, {}});
      }
      vector<pair<int, int>> v1, v2, v3, v4;
      vector<vector<pair<int, int>>> m1, m2, m3, m4;
      for (auto &i:_m1){
         sort(i.second.begin(), i.second.end(), [&](int x, int y){
            return a[x].y<a[y].y;
         });
         v1.push_back(i.first);
         m1.emplace_back();
         for (auto &j:i.second) m1.back().emplace_back(a[j].y, j);
      }
      for (auto &i:_m2){
         sort(i.second.begin(), i.second.end(), [&](int x, int y){
            return a[x].x<a[y].x;
         });
         v2.push_back(i.first);
         m2.emplace_back();
         for (auto &j:i.second) m2.back().emplace_back(a[j].x, j);
      }
      for (auto &i:_m3){
         sort(i.second.begin(), i.second.end(), [&](int x, int y){
            return a[x].x<a[y].x;
         });
         v3.push_back(i.first);
         m3.emplace_back();
         for (auto &j:i.second) m3.back().emplace_back(a[j].x, j);
      }
      for (auto &i:_m4){
         sort(i.second.begin(), i.second.end(), [&](int x, int y){
            return a[x].x<a[y].x;
         });
         v4.push_back(i.first);
         m4.emplace_back();
         for (auto &j:i.second) m4.back().emplace_back(a[j].x, j);
      }
      for (int i=1; i<=n; ++i){
         id1[i]=lower_bound(v1.begin(), v1.end(), i1[i])-v1.begin();
         id2[i]=lower_bound(v2.begin(), v2.end(), i2[i])-v2.begin();
         id3[i]=lower_bound(v3.begin(), v3.end(), i3[i])-v3.begin();
         id4[i]=lower_bound(v4.begin(), v4.end(), i4[i])-v4.begin();
      }
      priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> pq;
      auto add_val=[&](int i){
         vector<pair<int, int>> &vv1=m1[id1[i]^1], &vv2=m2[id2[i]^1], &vv3=m3[id3[i]^1], &vv4=m4[id4[i]^1];
         if (i1[i].second==0) 
            p1[i]=lower_bound(vv1.begin(), vv1.end(), make_pair(a[i].x+f[i]*2, 0ll))-vv1.begin();
         else 
            p1[i]=lower_bound(vv1.begin(), vv1.end(), make_pair(a[i].x-f[i]*2, (int)1e18))-vv1.begin()-1;
         if (i2[i].second==0) 
            p2[i]=lower_bound(vv2.begin(), vv2.end(), make_pair(a[i].y+f[i]*2, 0ll))-vv2.begin();
         else 
            p2[i]=lower_bound(vv2.begin(), vv2.end(), make_pair(a[i].y-f[i]*2, (int)1e18))-vv2.begin()-1;
         if (i3[i].second==0) 
            p3[i]=lower_bound(vv3.begin(), vv3.end(), make_pair(a[i].x+f[i], 0ll))-vv3.begin();
         else 
            p3[i]=lower_bound(vv3.begin(), vv3.end(), make_pair(a[i].x-f[i], (int)1e18))-vv3.begin()-1;
         if (i4[i].second==0) 
            p4[i]=lower_bound(vv4.begin(), vv4.end(), make_pair(a[i].x+f[i], 0ll))-vv4.begin();
         else 
            p4[i]=lower_bound(vv4.begin(), vv4.end(), make_pair(a[i].x-f[i], (int)1e18))-vv4.begin()-1;
         if (0<=p1[i] && p1[i]<(int)vv1.size()) pq.push({dist(i, vv1[p1[i]].second), {i, 1}});
         if (0<=p2[i] && p2[i]<(int)vv2.size()) pq.push({dist(i, vv2[p2[i]].second), {i, 2}});
         if (0<=p3[i] && p3[i]<(int)vv3.size()) pq.push({dist(i, vv3[p3[i]].second), {i, 3}});
         if (0<=p4[i] && p4[i]<(int)vv4.size()) pq.push({dist(i, vv4[p4[i]].second), {i, 4}});
      };
      memset(f, 0x3f, sizeof f);
      f[1]=0; add_val(1);
      while (pq.size()){
         int i=pq.top().second.first, d=pq.top().second.second, val=pq.top().first; pq.pop();
         vector<pair<int, int>> &vv=d==1?m1[id1[i]^1]:d==2?m2[id2[i]^1]:d==3?m3[id3[i]^1]:m4[id4[i]^1];
         int &p=d==1?p1[i]:d==2?p2[i]:d==3?p3[i]:p4[i];
         pair<int, int> &ii=d==1?i1[i]:d==2?i2[i]:d==3?i3[i]:i4[i];
         int j=vv[p].second;
         if (f[j]>1e18){
            f[j]=val;
            add_val(j);
         }
         if (ii.second==0) ++p;
         else --p;
         if (0<=p && p<(int)vv.size()) pq.push({dist(i, vv[p].second), {i, d}});
      }
      // for (int i=1; i<=n; ++i) if (f[i]<1e18) cout << i << ' ';
      // cout << '\n';
      ans=max(ans, accumulate(f+1, f+n+1, 0ll, [&](int x, int y){ return x+(y<1e18); }));
   };
   auto rotate=[&](){
      for (int i=1; i<=n; ++i) a[i]=Point(-a[i].y, a[i].x);
   };
   for (int i=1; i<=4; ++i){
      calc();
      rotate();
   }
   cout << ans << '\n';
   return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 8 / 8
• Subtask 3: 6 / 6
• Subtask 4: 6 / 6
• Subtask 5: 0 / 12
• Subtask 6: 0 / 32
• Subtask 7: 0 / 31