Submission #1170138

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170138		owieczka	Two Antennas (JOI19_antennas)	C++20	35 / 100	131 ms	19112 KiB

antennas

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int base = 1 << 18;

int mint[2 * base];
int maxt[2 * base];
int h[base];
pair<int, int> inv[base];
// set<pair<int, int>> reached;
void update(int c, bool on)
{
   if (on)
   {
      mint[c + base] = h[c];
      maxt[c + base] = h[c];
   }
   else 
   {
      mint[c + base] = 2e9;
      maxt[c + base] = -1;
   }
   c += base;
   c/=2;
   while (c)
   {
      maxt[c] = max(maxt[c*2], maxt[c*2+1]);
      mint[c] = min(mint[c*2], mint[c*2+1]);
      c/=2;
   }
}
pair<int,int> find(int b, int e)
{
   if (b < 0)b=0;
   if (e > base-1)e = base -1;
   b += base; e += base;
   b--; e++;
   int mn = INT_MAX;
   int mx = -1;
   while (b + 1 < e)
   {
      if (!(b & 1))
      {
         mn = min(mint[b+1], mn);
         mx = max(maxt[b+1], mx);
      }
      if ((e & 1))
      {
         mn = min(mint[e-1], mn);
         mx = max(maxt[e-1], mx);
      }
      b /= 2; e /= 2;
   }
   return {mn, mx};
}
int dp[2'002][2'002];

vector<pair<int, pair<int, int>>> query;

int main()
{
   ios::sync_with_stdio(0); cin.tie(0);
   int n, l, r;
   int q;
   cin >> n;

   for (int i = 1; i <= n; i++)
   {
      cin >> h[i] >> inv[i].first >> inv[i].second;
   }
   if (n <= 2e3)
   {
      for (int i = 0; i <= n; i++)
      {
         for (int j = 0; j <= n; j++)
            dp[i][j] = -1;
      }
      for (int d = 1; d < n; d++)
      {
         for (int i = 1; i + d <= n; i++)
         {
            dp[i][i+d] = max(dp[i+1][i+d], dp[i][i+d-1]);
            if (inv[i].first <= d && inv[i].second >= d && inv[i+d].first <= d && inv[i+d].second >= d)
               dp[i][i+d] = max(dp[i][i+d], abs(h[i] - h[i+d]));
         }
      }
      cin >> q;
      while (q--)
      {
         cin >> l >> r;
         cout << dp[l][r] << '\n';
      }
      return 0;
   }
   else
   {
      for (int i = 0; i < 2 *base; i++)
      {
         mint[i] = 2e9;
         maxt[i] = -1;
      }
      int ans = -1;
      for (int i = 1; i <= n; i++)
      {
         query.push_back({i - inv[i].second, {-1, i}});
         query.push_back({i - inv[i].first, {1, i}});
         query.push_back({i, {0, i}});
      }
      sort(query.begin(), query.end());
      for (auto i : query)
      {
         if (i.second.first == 1)
         {
            update(i.second.second, 0);
         }
         else if (i.second.first == -1)
         {
            update(i.second.second, 1);
         }
         else
         {
            auto v = find(i.second.second + inv[i.second.second].first, i.second.second + inv[i.second.second].second);
            ans = max(ans, h[i.second.second] - v.first);
            ans = max(ans, v.second - h[i.second.second]);
         }
      }
      cout << ans << '\n';
   }
}

• Subtask 1: 2 / 2
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 0 / 65