fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <climits>
  4. using namespace std;
  5.  
  6. class FenwickTree {
  7. private:
  8.     vector<long long> tree;
  9.     int size;
  10.  
  11. public:
  12.     FenwickTree(int n) : size(n) {
  13.         tree.resize(n + 1, 0);
  14.     }
  15.     void add(int idx, long long value) {
  16.         while (idx <= size) {
  17.             tree[idx] += value;
  18.             idx += idx & -idx;
  19.         }
  20.     }
  21.     long long sum(int idx) {
  22.         long long result = 0;
  23.         while (idx > 0) {
  24.             result += tree[idx];
  25.             idx -= idx & -idx;
  26.         }
  27.         return result;
  28.     }
  29.     void rangeAdd(int left, int right, long long value) {
  30.         add(left, value);
  31.         add(right + 1, -value);
  32.     }
  33.  
  34.     long long pointQuery(int idx) {
  35.         return sum(idx);
  36.     }
  37. };
  38.  
  39. long long skipUpdate(int N, int Q, vector<vector<int>>& updates) {
  40.  
  41.     FenwickTree fenwick(N);
  42.  
  43.     for (const auto& update : updates) {
  44.         int L = update[0];
  45.         int R = update[1];
  46.         int X = update[2];
  47.         fenwick.rangeAdd(L, R, X);
  48.     }
  49.  
  50.     vector<long long> fullArray(N + 1);
  51.     for (int i = 1; i <= N; ++i) {
  52.         fullArray[i] = fenwick.pointQuery(i);
  53.     }
  54.  
  55.     long long minMaxValue = LLONG_MAX;
  56.  
  57.     for (const auto& update : updates) {
  58.         int L = update[0];
  59.         int R = update[1];
  60.         int X = update[2];
  61.  
  62.         fenwick.rangeAdd(L, R, -X);
  63.  
  64.         long long currentMax = LLONG_MIN;
  65.         for (int i = 1; i <= N; ++i) {
  66.             currentMax = max(currentMax, fenwick.pointQuery(i));
  67.         }
  68.  
  69.         minMaxValue = min(minMaxValue, currentMax);
  70.  
  71.         fenwick.rangeAdd(L, R, X);
  72.     }
  73.  
  74.     return minMaxValue;
  75. }
  76.  
  77. int main() {
  78.     int T;
  79.     cin >> T;
  80.  
  81.     while (T--) {
  82.         int N, Q;
  83.         cin >> N >> Q;
  84.  
  85.         vector<vector<int>> updates(Q, vector<int>(3));
  86.         for (int i = 0; i < Q; ++i) {
  87.             cin >> updates[i][0] >> updates[i][1] >> updates[i][2];
  88.         }
  89.  
  90.         cout << skipUpdate(N, Q, updates) << endl;
  91.     }
  92.  
  93.     return 0;
  94. }
  95.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
1
5
3
3 4 2
2 3 4
1 5 10
stdout
copy 
6
https://ideone.com/nq5EiF
language:
C++14 (gcc 8.3)
created:
10 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!