Submission #1231116

#	Time	Username	Problem	Language	Result	Execution time	Memory
1231116		bachkahp	Art Exhibition (JOI18_art)	C++20	100 / 100	227 ms	20412 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 = 1e6 + 4;
int n, st[ma * 4], prefix[ma];
pair<int, int> a[ma];
vector<int> v;

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

void pre()
{
  for (int i = 1; i <= n; i++) prefix[i] = prefix[i - 1] + a[i].se;
}

void update(int id, int l, int r, int pos, int val)
{
  if (l == r)
  {
    st[id] = val;
    return;
  }

  int mid = (l + r) / 2;
  if (pos <= mid) update(id * 2, l, mid, pos, val);
  else update(id * 2 + 1, mid + 1, r, pos, val);

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

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

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

void solve()
{

  sort(a + 1, a + 1 + n);
  pre();
  int res = LLONG_MIN;
  for (int i = 1; i <= n; i++) res = max(res, a[i].se);
  for (int i = 1; i <= n; i++)
  {
    int tmp = prefix[i] - a[i].fi + get(1, 0, n, 0, i - 1);
    res = max(res, tmp);
    update(1, 0, n, i, a[i].fi - prefix[i - 1]);
  }

  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:70:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |     freopen(task ".INP", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
art.cpp:71:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |     freopen(task ".OUT", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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