Submission #1106746

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106746		vjudge1	Art Exhibition (JOI18_art)	C++17	100 / 100	192 ms	32328 KiB

art

#include <bits/stdc++.h>
#define int long long
#define ll long long
#define all(lpv) lpv.begin(), lpv.end()
#define fi first
#define se second

using namespace std;

typedef pair<int,int> pii;
const int N = 1e6 + 25;
const int oo = -1e16;
const int mod = 1e9 + 7;

int n, a[N], b[N];

namespace AC{
  int pos[N], s[N], st[N << 1];

  void update(int i,int x){
    i += n - 1;
    st[i] = x;
    while(i > 1){
      i /= 2;
      st[i] = max(st[i << 1], st[i << 1|1]);
    }
  }

  int get(int l,int r){
    if(l > r) return oo;
    r++;
    int ret = oo;
    for(l += n - 1, r += n - 1; l < r; l /= 2, r /= 2){
      if(l & 1) ret = max(ret, st[l ++]);
      if(r & 1) ret = max(ret, st[-- r]);
    }
    return ret;
  }
  void solve(){
    for(int i = 1; i <= n; i ++) pos[i] = i;
    sort(pos + 1, pos + n + 1, [&](int x,int y){return a[x] < a[y];});
    for(int i = 1; i <= 2 * n; i ++) st[i] = oo;

    for(int t = 1; t <= n; t ++){
      s[t] = s[t - 1] + b[pos[t]];
    }

    int ans = oo;
    update(1, -s[0] + a[pos[1]]);
    for(int t = 1; t <= n; t ++){
      int i = pos[t];
      ans = max(ans, get(1, t) + s[t] - a[pos[t]]);
      update(t + 1, -s[t] + a[pos[t + 1]]);
    }
    cout << ans;
  }
}


signed main() {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  #define task "v"
  if(fopen(task ".inp","r")){
    freopen(task ".inp","r",stdin);
    freopen(task ".out","w",stdout);
  }

  cin >> n;
  for(int i = 1; i <= n; i ++){
    cin >> a[i] >> b[i];
  }
  AC :: solve();

}

Compilation message (stderr)

art.cpp: In function 'void AC::solve()':
art.cpp:51:11: warning: unused variable 'i' [-Wunused-variable]
   51 |       int i = pos[t];
      |           ^
art.cpp: In function 'int main()':
art.cpp:64:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |     freopen(task ".inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
art.cpp:65:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |     freopen(task ".out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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