Submission #1131129

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131129		huutuan	IOI Fever (JOI21_fever)	C++20	100 / 100	3583 ms	150196 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];
pair<int, int> i1[N], i2[N], i3[N], i4[N];
int id1[N], id2[N], id3[N], id4[N];
int vis[N][5], nxt[N][5];

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);
      }
      memset(nxt, -1, sizeof nxt);
      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){
         if (b[i].y){
            _m1[i1[i]].push_back(i);
         }
         if (b[i].x){
            _m2[i2[i]].push_back(i);
         }
         _m3[i3[i]].push_back(i);
         _m4[i4[i]].push_back(i);
         _m1.insert({i1[i], {}});
         _m2.insert({i2[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=0; i<(int)m1.size(); ++i){
         if (i&1) for (int j=1; j<(int)m1[i].size(); ++j) nxt[m1[i][j-1].second][1]=m1[i][j].second;
         else for (int j=1; j<(int)m1[i].size(); ++j) nxt[m1[i][j].second][1]=m1[i][j-1].second;
      }
      for (int i=0; i<(int)m2.size(); ++i){
         if (i&1) for (int j=1; j<(int)m2[i].size(); ++j) nxt[m2[i][j-1].second][2]=m2[i][j].second;
         else for (int j=1; j<(int)m2[i].size(); ++j) nxt[m2[i][j].second][2]=m2[i][j-1].second;
      }
      for (int i=0; i<(int)m3.size(); ++i){
         if (i&1) for (int j=1; j<(int)m3[i].size(); ++j) nxt[m3[i][j-1].second][3]=m3[i][j].second;
         else for (int j=1; j<(int)m3[i].size(); ++j) nxt[m3[i][j].second][3]=m3[i][j-1].second;
      }
      for (int i=0; i<(int)m4.size(); ++i){
         if (i&1) for (int j=1; j<(int)m4[i].size(); ++j) nxt[m4[i][j-1].second][4]=m4[i][j].second;
         else for (int j=1; j<(int)m4[i].size(); ++j) nxt[m4[i][j].second][4]=m4[i][j-1].second;
      }
      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();
         memset(vis[i], 0, sizeof vis[i]);
      }
      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){
         int p1, p2, p3, p4;
         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=lower_bound(vv1.begin(), vv1.end(), make_pair(a[i].y+f[i]*2, 0ll))-vv1.begin();
         else
            p1=lower_bound(vv1.begin(), vv1.end(), make_pair(a[i].y-f[i]*2, (int)1e18))-vv1.begin()-1;
         if (i2[i].second==0)
            p2=lower_bound(vv2.begin(), vv2.end(), make_pair(a[i].x+f[i]*2, 0ll))-vv2.begin();
         else
            p2=lower_bound(vv2.begin(), vv2.end(), make_pair(a[i].x-f[i]*2, (int)1e18))-vv2.begin()-1;
         if (i3[i].second==0)
            p3=lower_bound(vv3.begin(), vv3.end(), make_pair(a[i].x+f[i], 0ll))-vv3.begin();
         else
            p3=lower_bound(vv3.begin(), vv3.end(), make_pair(a[i].x-f[i], (int)1e18))-vv3.begin()-1;
         if (i4[i].second==0)
            p4=lower_bound(vv4.begin(), vv4.end(), make_pair(a[i].x+f[i], 0ll))-vv4.begin();
         else
            p4=lower_bound(vv4.begin(), vv4.end(), make_pair(a[i].x-f[i], (int)1e18))-vv4.begin()-1;
         if (b[i].y && 0<=p1 && p1<(int)vv1.size()) pq.push({dist(i, vv1[p1].second), {vv1[p1].second, 1}});
         if (b[i].x && 0<=p2 && p2<(int)vv2.size()) pq.push({dist(i, vv2[p2].second), {vv2[p2].second, 2}});
         if (0<=p3 && p3<(int)vv3.size()) pq.push({dist(i, vv3[p3].second), {vv3[p3].second, 3}});
         if (0<=p4 && p4<(int)vv4.size()) pq.push({dist(i, vv4[p4].second), {vv4[p4].second, 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();
         if (vis[i][d]) continue;
         vis[i][d]=1;
         if (f[i]>1e18){
            f[i]=val;
            add_val(i);
         }
         if (nxt[i][d]!=-1) pq.push({val+dist(i, nxt[i][d]), {nxt[i][d], 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: 12 / 12
• Subtask 6: 32 / 32
• Subtask 7: 31 / 31