oj.uz

Submission #1035928

# Submission time Handle Problem Language Result Execution time Memory
1035928 2024-07-26T19:38:56 Z pera Divide and conquer (IZhO14_divide) C++17
17 / 100
 3 ms 5980 KB 
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 1;
int n , ans = 0 , SZ;
vector<int> x(N) , g(N) , e(N) , sum_e(N) , sum_g(N) , h(N) , t(N);
void upd(int u , int x){
   assert(u <= SZ);
   while(u <= SZ){
      t[u] = min(t[u] , x);
      u += u&-u;
   }
}
int GET(int u){
   assert(u <= SZ);
   int val = 1e18;
   while(u > 0){
      val = min(val , t[u]);
      u -= u&-u;
   }
   return val;
}
void solve(int l , int r){
   if(l > r){
      return;
   }
   SZ = r - l + 1;
   int m = (l + r) / 2;
   for(int i = l;i <= r;i ++){
      sum_e[i] = sum_e[i - 1] + e[i];
      sum_g[i] = sum_g[i - 1] + g[i];
   }
   vector<pair<int , int>> v , u;
   for(int i = l;i <= r;i ++){
      if(i < m){
         v.push_back({x[i - 1] - sum_e[i - 1] , i});
         u.push_back({sum_e[i - 1] - x[i] , i});
      }else{
         v.push_back({x[i + 1] - sum_e[i] , i});
         u.push_back({sum_e[i] - x[i] , i});
      }
   }
   sort(v.begin() , v.end());
   sort(u.begin() , u.end());
   for(int i = 0;i < (int)u.size();i ++){
      h[u[i].second] = (i == 0 ? 1 : h[u[i - 1].second] + (u[i].first != u[i - 1].first));
   }
   int mx = 0;
   for(auto [_value , id] : v){
      //cout << id << " " << h[id] << " " << sum_g[id - 1] << endl;
      if(id < m){
         upd(h[id] , sum_g[id - 1]);
      }else{
         ans = max(ans , sum_g[id] - GET(h[id]));
         if(x[id + 1] - x[m - 1] >= sum_e[id] - sum_e[m - 1] && sum_e[id] - sum_e[m - 1] > x[id] - x[m]){
            ans = max(ans , sum_g[id] - sum_g[m - 1]);
         }
      }
   }
  // cout << endl;
   for(int i = l;i <= r;i ++){
      sum_e[i] = sum_g[i] = h[i] = 0;
   }
   for(int i = 1;i <= r - l + 1;i ++){
      t[i] = 1e18;
   }
   //cout << l << " " << m << " " << r << " " << mx << endl;
   solve(l , m - 1);
   solve(m + 1 , r);
}
main(){
   cin >> n;
   for(int i = 1;i <= n;i ++){
      cin >> x[i] >> g[i] >> e[i];
      t[i] = 1e18;
   }
   x[n + 1] = 1e10;
   x[0] = -1e9;
   solve(1 , n);
   /*for(int L = 1;L <= n;L ++){
      for(int R = L;R <= n;R ++){
         int s = 0 , se = 0;
         for(int i = L;i <= R;i ++){
            se += e[i];
            s += g[i];
         }
         if(x[R + 1] - x[L - 1] >= se && se > x[R] - x[L]){
            ans = max(ans , s);
         }
      }
   }*/
   cout << ans << endl;
}

Compilation message

divide.cpp: In function 'void solve(long long int, long long int)':
divide.cpp:48:8: warning: unused variable 'mx' [-Wunused-variable]
   48 |    int mx = 0;
      |        ^~
divide.cpp: At global scope:
divide.cpp:71:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   71 | main(){
      | ^~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5720 KB Output is correct
2 Correct 2 ms 5724 KB Output is correct
3 Correct 3 ms 5976 KB Output is correct
4 Correct 2 ms 5724 KB Output is correct
5 Correct 2 ms 5724 KB Output is correct
6 Correct 2 ms 5724 KB Output is correct
7 Correct 3 ms 5720 KB Output is correct
8 Correct 3 ms 5724 KB Output is correct
9 Correct 2 ms 5724 KB Output is correct
10 Correct 2 ms 5724 KB Output is correct
11 Correct 2 ms 5868 KB Output is correct
12 Correct 2 ms 5720 KB Output is correct

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5720 KB Output is correct
2 Correct 2 ms 5724 KB Output is correct
3 Correct 3 ms 5976 KB Output is correct
4 Correct 2 ms 5724 KB Output is correct
5 Correct 2 ms 5724 KB Output is correct
6 Correct 2 ms 5724 KB Output is correct
7 Correct 3 ms 5720 KB Output is correct
8 Correct 3 ms 5724 KB Output is correct
9 Correct 2 ms 5724 KB Output is correct
10 Correct 2 ms 5724 KB Output is correct
11 Correct 2 ms 5868 KB Output is correct
12 Correct 2 ms 5720 KB Output is correct
13 Correct 3 ms 5724 KB Output is correct
14 Correct 2 ms 5724 KB Output is correct
15 Correct 2 ms 5976 KB Output is correct
16 Correct 3 ms 5980 KB Output is correct
17 Correct 3 ms 5980 KB Output is correct
18 Incorrect 3 ms 5980 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #3
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5720 KB Output is correct
2 Correct 2 ms 5724 KB Output is correct
3 Correct 3 ms 5976 KB Output is correct
4 Correct 2 ms 5724 KB Output is correct
5 Correct 2 ms 5724 KB Output is correct
6 Correct 2 ms 5724 KB Output is correct
7 Correct 3 ms 5720 KB Output is correct
8 Correct 3 ms 5724 KB Output is correct
9 Correct 2 ms 5724 KB Output is correct
10 Correct 2 ms 5724 KB Output is correct
11 Correct 2 ms 5868 KB Output is correct
12 Correct 2 ms 5720 KB Output is correct
13 Correct 3 ms 5724 KB Output is correct
14 Correct 2 ms 5724 KB Output is correct
15 Correct 2 ms 5976 KB Output is correct
16 Correct 3 ms 5980 KB Output is correct
17 Correct 3 ms 5980 KB Output is correct
18 Incorrect 3 ms 5980 KB Output isn't correct
19 Halted 0 ms 0 KB -