oj.uz

Submission #582047

# Submission time Handle Problem Language Result Execution time Memory
582047 2022-06-23T10:11:32 Z AlexLuchianov Arranging Tickets (JOI17_arranging_tickets) C++14
0 / 100
 1 ms 320 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cassert>

using ll = long long;

class SegmentTree{
private:
  std::vector<ll> aint;
  std::vector<ll> lazy;
public:
  SegmentTree(int n){
    aint.resize(1 + 4 * n);
    lazy.resize(1 + 4 * n);
  }
  void cleannode(int node, int from, int to){
    if(lazy[node] == 0)
      return ;
    if(from < to){
      int mid = (from + to) / 2;
      lazy[node * 2] += lazy[node];
      lazy[node * 2  + 1] += lazy[node];
    }
    aint[node] += lazy[node];
    lazy[node] = 0;
  }

  void computenode(int node, int from, int to){
    aint[node] = std::max(aint[node * 2], aint[node * 2 + 1]);
  }

  void update(int node, int from, int to, int x, int y, ll val){
    if(from == x && to == y){
      lazy[node] += val;
      cleannode(node, from, to);
    } else {
      int mid = (from + to) / 2;
      cleannode(node * 2, from, mid);
      cleannode(node * 2 + 1, mid + 1, to);

      if(x <= mid)
        update(node * 2, from, mid, x, std::min(y, mid), val);
      if(mid + 1 <= y)
        update(node * 2 + 1, mid + 1, to, std::max(mid + 1, x), y, val);
      computenode(node, from, to);
    }
  }

  ll query(int node, int from, int to, int x, int y){
    if(y < x)
      return 0;

    cleannode(node, from, to);
    
    if(from == x && to == y)
      return aint[node];
    else {
      int mid = (from + to) / 2;
      if(x <= mid && y <= mid)
        return query(node * 2, from, mid, x, y);
      else if(mid + 1 <= x && mid + 1 <= y)
        return query(node * 2 + 1, mid + 1, to, x, y);
      else
        return std::max(query(node * 2, from, mid, x, mid), query(node * 2 + 1, mid + 1, to, mid + 1, y));
    }
  }
};

class Event{
public:
  int x;
  int y;
  int cost;
  ll prio;
  bool operator < (Event const oth) {
    return prio < oth.prio;
  }
};

int const nmax = 200000;

int main() {
  std::ios::sync_with_stdio(0);
  std::cin.tie(0);

  int n, m;
  std::cin >> n >> m;
  std::vector<Event> queries;
  std::vector<ll> acc(1 + n), pref(1 + n), suff(1 + n);
  for(int i = 1;i <= m; i++) {
    int x, y, cost;
    std::cin >> x >> y >> cost;
    if(y < x) std::swap(x, y);
    y--;
    queries.push_back({x, y, cost, 0}); 
    acc[x] += cost;
    acc[y + 1] -= cost;
  }
  for(int i = 2;i <= n; i++)
    acc[i] += acc[i - 1];
  for(int i = 1;i <= n; i++)
    pref[i] = suff[i] = acc[i];
  for(int i = 2;i <= n; i++)
    pref[i] = std::max(pref[i], pref[i - 1]);
  for(int i = n - 1; 1 <= i; i--)
    suff[i] = std::max(suff[i + 1], suff[i]);
  for(int i = 0; i < queries.size(); i++)
    queries[i].prio = std::max(pref[queries[i].x - 1], suff[queries[i].y + 1]);
  std::sort(queries.begin(), queries.end());
  SegmentTree aint(1 + n);
  for(int i = 0; i < queries.size(); i++) {
    aint.update(1, 1, n, queries[i].x, queries[i].y, queries[i].cost);
  }

  for(int i = 0; i < queries.size(); i++) {
    ll base = std::max(aint.query(1, 1, n, 1, queries[i].x - 1), aint.query(1, 1, n, queries[i].y + 1, n));
    ll internal = aint.query(1, 1, n, queries[i].x, queries[i].y);
    ll moves = std::min((internal - base) / 2, 1LL * queries[i].cost);
    if(moves < 0)
      break;
    aint.update(1, 1, n, 1, n, moves);
    aint.update(1, 1, n, queries[i].x, queries[i].y, -2 * moves);
  }
  std::cout << aint.query(1, 1, n, 1, n) << '\n';
  return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Incorrect 1 ms 320 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Incorrect 1 ms 320 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Incorrect 1 ms 320 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Incorrect 1 ms 320 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Incorrect 1 ms 320 KB Output isn't correct
13 Halted 0 ms 0 KB -