Submission #1230771

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230771		bachkahp	Art Exhibition (JOI18_art)	C++20	0 / 100	0 ms	324 KiB

art

#include <bits/stdc++.h>
#define int long long
#define task "task"
#define fi first
#define se second
using namespace std;

const int ma = 5e5 + 4;
pair<int, int> a[ma];
int n;

struct node
{
  int ans, mi, sum;
} st[ma * 4];

void Read()
{
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> a[i].fi >> a[i].se;
}

node take(node a, node b)
{
  if (a.ans == LLONG_MIN) return b;
  if (b.ans == LLONG_MIN) return a;

  node ans;
  ans.sum = a.sum + b.sum;
  ans.mi = max(a.mi, b.mi);
  ans.ans = max({ans.sum - ans.mi, a.ans, b.ans});

  return ans;
}

void build(int id, int l, int r)
{
  if (l == r)
  {
    st[id].ans = a[l].se - a[l].fi;
    st[id].mi = a[l].fi;
    st[id].sum = a[l].se;
    return;
  }

  int mid = (l + r) / 2;
  build(id * 2, l, mid);
  build(id * 2 + 1, mid + 1, r);

  st[id] = take(st[id * 2], st[id * 2 + 1]);
}

node get(int id, int tl, int tr, int l, int r)
{
  if (l > tr || r < tl) return {LLONG_MIN, 0, 0};
  if (l <= tl && tr <= r) return st[id];

  int mid = (tl + tr) / 2;
  node ansl = get(id * 2, tl, mid, l, r);
  node ansr = get(id * 2 + 1, mid + 1, tr, l, r);
  return take(ansl, ansr);
}

void solve()
{
  sort(a + 1, a + 1 + n);
  build(1, 1, n);

  int res = LLONG_MIN;
  for (int i = 1; i <= n; i++)
  {
    res = max(res, a[i].fi + get(1, 1, n, i, n).ans);
  }

  cout << res;
}

signed main()
{
  if(fopen(task ".INP", "r"))
  {
    freopen(task ".INP", "r", stdin);
    freopen(task ".OUT", "w", stdout);
  }
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  Read();
  solve();

  return 0;
}

Compilation message (stderr)

art.cpp: In function 'int main()':
art.cpp:82:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |     freopen(task ".INP", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
art.cpp:83:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |     freopen(task ".OUT", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 50