oj.uz

Submission #654511

# Submission time Handle Problem Language Result Execution time Memory
654511 2022-10-31T14:32:22 Z pauloamed Divide and conquer (IZhO14_divide) C++14
0 / 100
 1 ms 1108 KB 
#include<bits/stdc++.h>
using namespace std;

#define int long long

const int MAXN = 100000;

struct BIT{
  int n; vector<int> v;
  BIT(int m = 0):n(m + 2), v(vector<int>(n, LLONG_MAX)){}

  int query(int i){ int ans = LLONG_MAX;
    for(i++; i > 0; i -= i & (-i))
      ans = min(ans, v[i]);
    return ans;
  }

  void update(int i, int val){
    for(i++; i < n; i += i & (-i)) 
      v[i] = min(val, v[i]);
  }
};

BIT bit(MAXN);

int X[MAXN], G[MAXN], E[MAXN];

int idx(vector<int> &v, int x){
  int n = v.size();
  int id = lower_bound(v.begin(), v.end(), x) - v.begin();
  return n - 1 - id;
}

int idx(int v[], int i){
  if(i < 0) return 0;
  else return v[i];
}

int32_t main(){
  int n; cin >> n;
  vector<int> vals;

  {
    int e_accu = 0;
    for(int i = 0; i < n; ++i){
      cin >> X[i] >> G[i] >> E[i]; 
      X[i]++;
      if(i) E[i] += E[i - 1];
      if(i) G[i] += G[i - 1];

      int Iq = X[i] - E[i];
      int Iu = X[i] - idx(E, i - 1);

      vals.push_back(Iq);
      vals.push_back(Iu);
    }
  }

  vals.push_back(0);

  sort(vals.begin(), vals.end());
  vals.erase(unique(vals.begin(), vals.end()), vals.end());

  bit.update(idx(vals, 0), 0);

  int ans = 0;
  for(int i = 0; i < n; ++i){
    int Iq = X[i] - E[i];
    int Iu = X[i] - idx(E, i - 1);

    Iq = idx(vals, Iq);
    Iu = idx(vals, Iu);

    int best = bit.query(Iq);
    bit.update(Iu, G[i]);


    ans = max(ans, G[i] - best);
    ans = max(ans, G[i]);
  }
  cout << ans << "\n";
}

Compilation message

divide.cpp: In function 'int32_t main()':
divide.cpp:44:9: warning: unused variable 'e_accu' [-Wunused-variable]
   44 |     int e_accu = 0;
      |         ^~~~~~

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1108 KB Output is correct
2 Incorrect 1 ms 1108 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1108 KB Output is correct
2 Incorrect 1 ms 1108 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1108 KB Output is correct
2 Incorrect 1 ms 1108 KB Output isn't correct
3 Halted 0 ms 0 KB -