oj.uz

Submission #234803

# Submission time Handle Problem Language Result Execution time Memory
234803 2020-05-25T16:56:11 Z AlexLuchianov Two Antennas (JOI19_antennas) C++14
22 / 100
 624 ms 25816 KB 
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

int const nmax = 200000;
int const inf = 1000000005;

struct El{
  int h;
  int a;
  int b;
} v[1 + nmax];
int _queries[1 + nmax][2];
int sol[1 + nmax];

vector<int> events[1 + nmax];
vector<pair<int,int>> queries[1 + nmax];

class SegmentTree{
private:
  struct Node{
    int result;
    int smax;
    Node operator + (Node const &a) const {
      return {max(result, a.result), max(smax, a.smax)};
    }
  };
public:
  vector<Node> aint;
  vector<int> lazy;

  SegmentTree(int n){
    aint.resize(1 + 4 * n);
    lazy.resize(1 + 4 * n);
  }

  void build(int node, int from, int to){
    if(from < to){
      int mid = (from + to) / 2;
      build(node * 2, from, mid);
      build(node * 2 + 1, mid + 1, to);
    }
    aint[node] = {-inf, -inf};
  }

  void cleannode(int node, int from, int to){
    if(from < to){
      int mid = (from + to) / 2;
      lazy[node * 2] = max(lazy[node * 2], lazy[node]);
      lazy[node * 2 + 1] = max(lazy[node * 2 + 1], lazy[node]);
    }
    aint[node].result = max(aint[node].result, aint[node].smax + lazy[node]);
    lazy[node] = 0;
  }

  void computenode(int node, int from, int to){
    if(from < to){
      int mid = (from + to) / 2;
      aint[node] = aint[node * 2] + aint[node * 2 + 1];
    }
  }

  void update(int node, int from, int to, int x, int y, int val){
    if(x == from && to == y){
      lazy[node] = max(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, MIN(y, mid), val);
      if(mid + 1 <= y)
        update(node * 2 + 1, mid + 1, to, MAX(mid + 1, x), y, val);
      computenode(node, from, to);
    }
  }

  void setvalue(int node, int from, int to, int x, int val){
    if(from < to){
      int mid = (from + to) / 2;
      cleannode(node * 2, from, mid);
      cleannode(node * 2 + 1, mid + 1, to);
      if(x <= mid)
        setvalue(node * 2, from, mid, x, val);
      else
        setvalue(node * 2 + 1, mid + 1, to, x, val);
      computenode(node, from, to);
    } else {
      cleannode(node, from, to);
      aint[node].smax = val;
    }
  }

  int query(int node, int from, int to, int x, int y){
    cleannode(node, from, to);
    if(from == x && to == y)
      return aint[node].result;
    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 max(query(node * 2, from, mid, x, mid), query(node * 2 + 1, mid + 1, to, mid + 1, y));
    }
  }
};

void solve(int n, int q){
  for(int i = 1;i <= n; i++) {
    events[i].clear();
    queries[i].clear();
  }

  for(int i = 1; i <= n; i++) {
    if(i + v[i].a <= n)
      events[i + v[i].a].push_back(i);
    if(i + v[i].b + 1 <= n)
      events[i + v[i].b + 1].push_back(-i);
  }

  for(int i = 1; i <= q; i++)
    queries[_queries[i][1]].push_back({_queries[i][0], i});
  SegmentTree aint(1 + n);

  for(int i = 1; i <= n; i++)
    aint.setvalue(1, 1, n, i, -inf);

  for(int i = 1; i <= n; i++){
    for(int h = 0; h < events[i].size(); h++){
      int id = events[i][h];
      if(0 < id)
        aint.setvalue(1, 1, n, id, -v[id].h);
      else
        aint.setvalue(1, 1, n, -id, -inf);
    }

    int x = max(1, i - v[i].b);
    int y = i - v[i].a;
    if(x <= y)
      aint.update(1, 1, n, x, y, v[i].h);


    for(int h = 0; h < queries[i].size(); h++){
      int pos = queries[i][h].second;
      sol[pos] = max(sol[pos], aint.query(1, 1, n, queries[i][h].first, i));
    }
  }
}

int oth(int n, int pos){
  return n - pos + 1;
}

int main()
{

  ios::sync_with_stdio(0);
  cin.tie(0);


  int n;
  cin >> n;
  for(int i = 1;i <= n; i++)
    cin >> v[i].h >> v[i].a >> v[i].b;
  int q;
  cin >> q;
  for(int i = 1;i <= q; i++)
    cin >> _queries[i][0] >> _queries[i][1];
  for(int i = 1;i <= q; i++)
    sol[i] = -1;

  solve(n, q);

  for(int i = 1;i <= n; i++)
    if(i < oth(n, i))
      swap(v[i], v[oth(n, i)]);
  for(int i = 1;i <= q; i++) {
    _queries[i][0] = oth(n, _queries[i][0]);
    _queries[i][1] = oth(n, _queries[i][1]);
    swap(_queries[i][0], _queries[i][1]);
  }

  solve(n, q);
  for(int i = 1;i <= q; i++)
    cout << sol[i] << '\n';

  return 0;
}

Compilation message

antennas.cpp: In member function 'void SegmentTree::cleannode(int, int, int)':
antennas.cpp:54:11: warning: unused variable 'mid' [-Wunused-variable]
       int mid = (from + to) / 2;
           ^~~
antennas.cpp: In member function 'void SegmentTree::computenode(int, int, int)':
antennas.cpp:64:11: warning: unused variable 'mid' [-Wunused-variable]
       int mid = (from + to) / 2;
           ^~~
antennas.cpp: In function 'void solve(int, int)':
antennas.cpp:138:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int h = 0; h < events[i].size(); h++){
                    ~~^~~~~~~~~~~~~~~~~~
antennas.cpp:152:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int h = 0; h < queries[i].size(); h++){
                    ~~^~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 9856 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 9856 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 547 ms 24208 KB Output is correct
2 Correct 624 ms 25772 KB Output is correct
3 Correct 408 ms 20924 KB Output is correct
4 Correct 615 ms 25696 KB Output is correct
5 Correct 255 ms 17164 KB Output is correct
6 Correct 616 ms 25788 KB Output is correct
7 Correct 531 ms 23696 KB Output is correct
8 Correct 579 ms 25816 KB Output is correct
9 Correct 81 ms 12328 KB Output is correct
10 Correct 576 ms 25720 KB Output is correct
11 Correct 365 ms 19964 KB Output is correct
12 Correct 572 ms 25684 KB Output is correct
13 Correct 499 ms 24980 KB Output is correct
14 Correct 473 ms 24376 KB Output is correct
15 Correct 462 ms 23820 KB Output is correct
16 Correct 437 ms 23852 KB Output is correct
17 Correct 499 ms 25424 KB Output is correct
18 Correct 480 ms 24148 KB Output is correct
19 Correct 493 ms 24268 KB Output is correct
20 Correct 481 ms 24320 KB Output is correct
21 Correct 450 ms 24396 KB Output is correct
22 Correct 470 ms 24428 KB Output is correct
23 Correct 479 ms 24424 KB Output is correct
24 Correct 428 ms 23376 KB Output is correct

Subtask #4
0 / 65.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 9856 KB Output isn't correct
2 Halted 0 ms 0 KB -