Submission #1169935

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169935		owieczka	Two Antennas (JOI19_antennas)	C++20	13 / 100	55 ms	17832 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];

void update(int c, bool on)
{
   if (on)
   {
      mint[c + base] = h[c];
      maxt[c + base] = h[c];
   }
   else 
   {
      mint[c + base] = INT_MAX;
      maxt[c + base] = -1;
   }
   c += base;
   while (c)
   {
      c/=2;
      maxt[c] = max(maxt[c*2], maxt[c*2+1]);
      mint[c] = min(mint[c*2], mint[c*2+1]);
   }
}
pair<int,int> find(int b, int e)
{
   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);
      }
   }
   return {mn, mx};
}
int dp[2'002][2'002];

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

   for (int i = 0; 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 = 0; 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-1][r-1] << '\n';
      }
      return 0;
   }
   else
   {
      //
   }
}

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